The Advice Complexity of a Class of Hard Online Problems

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

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

92 Downloads (Pure)

Resumé

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.
OriginalsprogEngelsk
TidsskriftTheory of Computing Systems
Vol/bind61
Udgave nummer4
Sider (fra-til)1128-1177
ISSN1432-4350
DOI
StatusUdgivet - 2017
BegivenhedInternational Symposium on Theoretical Aspects of Computer Science - TUM Garching, Gartching, Tyskland
Varighed: 4. mar. 20157. mar. 2015
Konferencens nummer: 42

Konference

KonferenceInternational Symposium on Theoretical Aspects of Computer Science
Nummer42
LokationTUM Garching
LandTyskland
ByGartching
Periode04/03/201507/03/2015

Fingeraftryk

Competitive Ratio
Online Algorithms
Independent Set
Upper bound
Class
Disjoint Paths
Vertex Cover
Complexity Classes
Dominating Set
Term
Upper and Lower Bounds
Strings
Entire
Higher Order
Sufficient
Lower bound
Imply
Necessary
Model
Knowledge

Emneord

  • online algorithms
  • advice complexity
  • complexity class
  • asymmetric string guessing
  • covering designs
  • Asymmetric Online Covering (AOC)

Citer dette

Boyar, Joan ; Favrholdt, Lene Monrad ; Kudahl, Christian ; Mikkelsen, Jesper With. / The Advice Complexity of a Class of Hard Online Problems. I: Theory of Computing Systems. 2017 ; Bind 61, Nr. 4. s. 1128-1177.
@article{3499667e546b4bffa789a0a1e447c335,
title = "The Advice Complexity of a Class of Hard Online Problems",
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{\"o}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{\'o}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{\"o}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.",
keywords = "online algorithms, advice complexity, complexity class, asymmetric string guessing, covering designs, Asymmetric Online Covering (AOC)",
author = "Joan Boyar and Favrholdt, {Lene Monrad} and Christian Kudahl and Mikkelsen, {Jesper With}",
year = "2017",
doi = "10.1007/s00224-016-9688-y",
language = "English",
volume = "61",
pages = "1128--1177",
journal = "Theory of Computing Systems",
issn = "1432-4350",
publisher = "Springer",
number = "4",

}

The Advice Complexity of a Class of Hard Online Problems. / Boyar, Joan; Favrholdt, Lene Monrad; Kudahl, Christian; Mikkelsen, Jesper With.

I: Theory of Computing Systems, Bind 61, Nr. 4, 2017, s. 1128-1177.

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

TY - JOUR

T1 - The Advice Complexity of a Class of Hard Online Problems

AU - Boyar, Joan

AU - Favrholdt, Lene Monrad

AU - Kudahl, Christian

AU - Mikkelsen, Jesper With

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

KW - online algorithms

KW - advice complexity

KW - complexity class

KW - asymmetric string guessing

KW - covering designs

KW - Asymmetric Online Covering (AOC)

U2 - 10.1007/s00224-016-9688-y

DO - 10.1007/s00224-016-9688-y

M3 - Journal article

VL - 61

SP - 1128

EP - 1177

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 4

ER -