License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2015.116
URN: urn:nbn:de:0030-drops-49086
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4908/
Boyar, Joan ;
Favrholdt, Lene M. ;
Kudahl, Christian ;
Mikkelsen, Jesper W.
Advice Complexity for a Class of 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. 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.
BibTeX - Entry
@InProceedings{boyar_et_al:LIPIcs:2015:4908,
author = {Joan Boyar and Lene M. Favrholdt and Christian Kudahl and Jesper W. Mikkelsen},
title = {{Advice Complexity for a Class of Online Problems}},
booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
pages = {116--129},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-78-1},
ISSN = {1868-8969},
year = {2015},
volume = {30},
editor = {Ernst W. Mayr and Nicolas Ollinger},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/4908},
URN = {urn:nbn:de:0030-drops-49086},
doi = {10.4230/LIPIcs.STACS.2015.116},
annote = {Keywords: online algorithms, advice complexity, asymmetric string guessing, advice complexity class AOC, covering designs}
}
|
Keywords: |
|
online algorithms, advice complexity, asymmetric string guessing, advice complexity class AOC, covering designs |
|
Collection: |
|
32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) |
|
Issue Date: |
|
2015 |
|
Date of publication: |
|
26.02.2015 |
