Preemptively Guessing the Center

Christian Konrad, Tigran Tonoyan

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

39 Downloads (Pure)

Abstract

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.
Original languageEnglish
Title of host publicationCombinatorial Optimization
Subtitle of host publication5th International Symposium, ISCO 2018, Marrakesh, Morocco, April 11-13, 2018, Revised Selected Papers
PublisherSpringer
Pages277-289
Number of pages13
ISBN (Electronic)9783319961514
ISBN (Print)9783319961507
DOIs
Publication statusPublished - 18 Jul 2018

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Nature
Volume10856
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Fingerprint Dive into the research topics of 'Preemptively Guessing the Center'. Together they form a unique fingerprint.

Cite this