The Advice Complexity of a Class of Hard Online Problems

Joan Boyar, Lene Monrad Favrholdt, Christian Kudahl, Jesper With Mikkelsen

Research output: Contribution to journalJournal articleResearchpeer-review

166 Downloads (Pure)

Abstract

The advice complexity of an online problem is a measure of how much knowledge of the future an online algorithm needs in order to achieve a certain competitive ratio. Using advice complexity, we define the first online complexity class, AOC. The class includes independent set, vertex cover, dominating set, and several others as complete problems. AOC-complete problems are hard, since a single wrong answer by the online algorithm can have devastating consequences. For each of these problems, we show that log(1+(c−1)c−1/cc)n=Θ(n/c) bits of advice are necessary and sufficient (up to an additive term of O(logn) ) to achieve a competitive ratio of c. The results are obtained by introducing a new string guessing problem related to those of Emek et al. (Theor. Comput. Sci. 412(24), 2642–2656 2011) and Böckenhauer et al. (Theor. Comput. Sci. 554, 95–108 2014). It turns out that this gives a powerful but easy-to-use method for providing both upper and lower bounds on the advice complexity of an entire class of online problems, the AOC-complete problems. Previous results of Halldórsson et al. (Theor. Comput. Sci. 289(2), 953–962 2002) on online independent set, in a related model, imply that the advice complexity of the problem is Θ(n/c). Our results improve on this by providing an exact formula for the higher-order term. For online disjoint path allocation, Böckenhauer et al. (ISAAC 2009) gave a lower bound of Ω(n/c) and an upper bound of O((nlogc)/c) on the advice complexity. We improve on the upper bound by a factor of logc . For the remaining problems, no bounds on their advice complexity were previously known.
Original languageEnglish
JournalTheory of Computing Systems
Volume61
Issue number4
Pages (from-to)1128-1177
ISSN1432-4350
DOIs
Publication statusPublished - 2017
EventInternational Symposium on Theoretical Aspects of Computer Science - TUM Garching, Gartching, Germany
Duration: 4. Mar 20157. Mar 2015
Conference number: 42

Conference

ConferenceInternational Symposium on Theoretical Aspects of Computer Science
Number42
LocationTUM Garching
Country/TerritoryGermany
CityGartching
Period04/03/201507/03/2015

Fingerprint

Dive into the research topics of 'The Advice Complexity of a Class of Hard Online Problems'. Together they form a unique fingerprint.

Cite this