TY - GEN
T1 - Preemptively Guessing the Center
AU - Konrad, Christian
AU - Tonoyan, Tigran
PY - 2018/7/18
Y1 - 2018/7/18
N2 - An online algorithm is typically unaware of the length of the input request sequence that it is called upon. Consequently, it cannot determine whether it has already processed most of its input or whether the bulk of work is still ahead. In this paper, we are interested in whether some sort of orientation within the request sequence is nevertheless possible. Our objective is to preemptively guess the center of a request sequence of unknown length n: While processing the input, the online algorithm maintains a guess for the central position n/2 and is only allowed to update its guess to the position of the current element under investigation. We show that there is a randomized algorithm that in expectation places the guess at a distance of 0.172n from the central position n/2, and we prove that this is best possible. We also give upper and lower bounds for a natural extension to weighted sequences. This problem has an application to preemptively partitioning integer sequences and is connected to the online bidding problem.
AB - An online algorithm is typically unaware of the length of the input request sequence that it is called upon. Consequently, it cannot determine whether it has already processed most of its input or whether the bulk of work is still ahead. In this paper, we are interested in whether some sort of orientation within the request sequence is nevertheless possible. Our objective is to preemptively guess the center of a request sequence of unknown length n: While processing the input, the online algorithm maintains a guess for the central position n/2 and is only allowed to update its guess to the position of the current element under investigation. We show that there is a randomized algorithm that in expectation places the guess at a distance of 0.172n from the central position n/2, and we prove that this is best possible. We also give upper and lower bounds for a natural extension to weighted sequences. This problem has an application to preemptively partitioning integer sequences and is connected to the online bidding problem.
U2 - 10.1007/978-3-319-96151-4_24
DO - 10.1007/978-3-319-96151-4_24
M3 - Conference Contribution (Conference Proceeding)
SN - 9783319961507
T3 - Lecture Notes in Computer Science
SP - 277
EP - 289
BT - Combinatorial Optimization
PB - Springer
ER -