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 -