Document Open Access Logo

Advice Complexity for a Class of Online Problems

Authors Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Jesper W. Mikkelsen

PDF
Thumbnail PDF

File

LIPIcs.STACS.2015.116.pdf
  • Filesize: 0.66 MB
  • 14 pages

Document Identifiers

Author Details

Joan Boyar
Lene M. Favrholdt
Christian Kudahl
Jesper W. Mikkelsen

Cite AsGet BibTex

Joan Boyar, Lene M. Favrholdt, Christian Kudahl, and Jesper W. Mikkelsen. Advice Complexity for a Class of Online Problems. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 116-129, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.STACS.2015.116

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. We determine the advice complexity of a number of hard online problems including independent set, vertex cover, dominating set and several others. These 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\left(1+\frac{(c-1)^{c-1}}{c^{c}}\right)n=\Theta (n/c) bits of advice are necessary and sufficient (up to an additive term of O(\log n)) to achieve a competitive ratio of c. This is done by introducing a new string guessing problem related to those of Emek et al. (TCS 2011) and Böckenhauer et al. (TCS 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. Previous results of Halldórsson et al. (TCS 2002) on online independent set, in a related model, imply that the advice complexity of the problem is \Theta (n/c). Our results improve on this by providing an exact formula for the higher-order term. Böckenhauer et al. (ISAAC 2009) gave a lower bound of \Omega (n/c) and an upper bound of O((n\log c)/c) on the advice complexity of online disjoint path allocation. We improve on the upper bound by a factor of $\log c$. For the remaining problems, no bounds on their advice complexity were previously known.
Keywords
  • online algorithms
  • advice complexity
  • asymmetric string guessing
  • advice complexity class AOC
  • covering designs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor. The online set cover problem. SIAM J. Comput., 39(2):361-370, 2009. Google Scholar
  2. Kfir Barhum. Tight bounds for the advice complexity of the online minimum steiner tree problem. In SOFSEM, pages 77-88, 2014. Google Scholar
  3. Kfir Barhum, Hans-Joachim Böckenhauer, Michal Forišek, Heidi Gebauer, Juraj Hromkovič, Sacha Krug, Jasmin Smula, and Björn Steffen. On the power of advice and randomization for the disjoint path allocation problem. In SOFSEM, pages 89-101, 2014. Google Scholar
  4. Maria Paola Bianchi, Hans-Joachim Böckenhauer, Juraj Hromkovič, and Lucia Keller. Online coloring of bipartite graphs with and without advice. Algorithmica, 70(1):92-111, 2014. Google Scholar
  5. Hans-Joachim Böckenhauer, Juraj Hromkovič, Dennis Komm, Sacha Krug, Jasmin Smula, and Andreas Sprock. The string guessing problem as a method to prove lower bounds on the advice complexity. Theor. Comput. Sci., 2014. Google Scholar
  6. Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královič, and Richard Královič. On the advice complexity of the k-server problem. In ICALP (1), pages 207-218, 2011. Google Scholar
  7. Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královič, Richard Královič, and Tobias Mömke. On the advice complexity of online problems. In ISAAC, pages 331-340, 2009. Google Scholar
  8. Hans-Joachim Böckenhauer, Dennis Komm, Richard Královič, and Peter Rossmanith. The online knapsack problem: Advice and randomization. Theor. Comput. Sci., 527:61-72, 2014. Google Scholar
  9. Joan Boyar, Lene M. Favrholdt, Christian Kudahl, and Jesper W. Mikkelsen. The Advice Complexity of a Class of Hard Online Problems. arXiv, 1408.7033 (cs.DS), August 2014. Google Scholar
  10. Joan Boyar, Shahin Kamali, Kim S. Larsen, and Alejandro López-Ortiz. On the list update problem with advice. In LATA, pages 210-221, 2014. Google Scholar
  11. Joan Boyar, Shahin Kamali, Kim S. Larsen, and Alejandro López-Ortiz. Online bin packing with advice. In STACS, pages 174-186, 2014. Full paper to appear in Algorithmica. Google Scholar
  12. Marc Demange and Vangelis Th. Paschos. On-line vertex-covering. Theor. Comput. Sci., 332(1-3):83-108, 2005. Google Scholar
  13. Jeffrey H. Dinitz and Douglas R. Stinson, editors. Contemporary Design Theory: a Collection of Surveys. Wiley-Interscience series in discrete mathematics and optimization. Wiley, New York, 1992. Google Scholar
  14. Stefan Dobrev, Rastislav Královič, and Richard Královič. Independent set with advice: The impact of graph knowledge - (extended abstract). In WAOA, pages 2-15, 2012. Google Scholar
  15. Stefan Dobrev, Rastislav Královič, and Dana Pardubská. Measuring the problem-relevant information in input. RAIRO - Theor. Inf. Appl., 43(3):585-613, 2009. Google Scholar
  16. Yuval Emek, Pierre Fraigniaud, Amos Korman, and Adi Rosén. Online computation with advice. Theor. Comput. Sci., 412(24):2642-2656, 2011. Google Scholar
  17. Paul Erdős and Joel Spencer. Probabilistic Methods in Combinatorics. Academic Press, 1974. Google Scholar
  18. Michal Forišek, Lucia Keller, and Monika Steinová. Advice complexity of online coloring for paths. In LATA, pages 228-239, 2012. Google Scholar
  19. Sushmita Gupta, Shahin Kamali, and Alejandro López-Ortiz. On advice complexity of the k-server problem under sparse metrics. In SIROCCO, pages 55-67, 2013. Google Scholar
  20. Magnús M. Halldórsson. Online coloring known graphs. Electronic J. of Combinatorics, 7(R7), 2000. Google Scholar
  21. Magnús M. Halldórsson, Kazuo Iwama, Shuichi Miyazaki, and Shiro Taketomi. Online independent sets. Theor. Comput. Sci., 289(2):953-962, 2002. Google Scholar
  22. Magnús M. Halldórsson and Hadas Shachnai. Return of the boss problem: Competing online against a non-adaptive adversary. In FUN, pages 237-248, 2010. Google Scholar
  23. Johan Håstad. Clique is hard to approximate within n^1-ε. Acta Math., 182(1):105-142, 1999. Google Scholar
  24. Juraj Hromkovič, Rastislav Královič, and Richard Královič. Information complexity of online problems. In MFCS, pages 24-36, 2010. Google Scholar
  25. Sandy Irani. Coloring inductive graphs on-line. Algorithmica, 11(1):53-72, 1994. Google Scholar
  26. Anna R. Karlin, Mark S. Manasse, Larry Rudolph, and Daniel D. Sleator. Competitive snoopy caching. Algorithmica, 3:77-119, 1988. Google Scholar
  27. Dennis Komm, Richard Královič, and Tobias Mömke. On the advice complexity of the set cover problem. In CSR, pages 241-252, 2012. Google Scholar
  28. Shuichi Miyazaki. On the advice complexity of online bipartite matching and online stable marriage. Inf. Process. Lett., 114(12):714-717, 2014. Google Scholar
  29. Ran Raz and Shmuel Safra. A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In STOC, pages 475-484, 1997. Google Scholar
  30. Marc P. Renault, Adi Rosén, and Rob van Stee. Online algorithms with advice for bin packing and scheduling problems. CoRR, abs/1311.7589, 2013. Google Scholar
  31. Sebastian Seibert, Andreas Sprock, and Walter Unger. Advice complexity of the online coloring problem. In CIAC, pages 345-357, 2013. Google Scholar
  32. Daniel D. Sleator and Robert E. Tarjan. Amortized efficiency of list update and paging rules. Commun. ACM, 28(2):202-208, 1985. Google Scholar
  33. Wen-Guey Tzeng. On-line dominating set problems for graphs. In D.-Z. Ding and Pardalos, editors, Handbook of Combinatorial Optimization. Kluwer Academic Publishers, Boston, 1998. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact