Recently, advice complexity has been introduced as a new framework to analyze online algorithms. There, an online algorithm has access to an infinite binary advice tape during the computation. The contents of this tape were prepared beforehand by an omniscient oracle. One is interested in analyzing the number of accessed advice bits necessary and/or sufficient to achieve a certain solution quality. Among others, the bit guessing problem was analyzed in this framework. Here, an algorithm needs to guess a binary string bit by bit, either with or without getting immediate feedback after each bit. The bit guessing problem can be used to obtain lower bounds on the advice complexity of a variety of other online problems. In this paper, we analyze the difference between the two bit guessing variants. More precisely, we show that getting feedback after each request helps save advice bits when we allow errors to be made. This is by no means obvious – for optimality, both problem versions need the same amount of advice, and without advice, knowing the history does not help at all.
Accepté le :
DOI : 10.1051/ita/2015003
Mots-clés : Online computation, bit guessing, advice complexity
@article{ITA_2015__49_2_139_0,
author = {Krug, Sacha},
title = {Towards using the history in online computation with advice},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {139--152},
publisher = {EDP-Sciences},
volume = {49},
number = {2},
year = {2015},
doi = {10.1051/ita/2015003},
mrnumber = {3373812},
zbl = {1336.68306},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/ita/2015003/}
}
TY - JOUR AU - Krug, Sacha TI - Towards using the history in online computation with advice JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2015 SP - 139 EP - 152 VL - 49 IS - 2 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita/2015003/ DO - 10.1051/ita/2015003 LA - en ID - ITA_2015__49_2_139_0 ER -
%0 Journal Article %A Krug, Sacha %T Towards using the history in online computation with advice %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2015 %P 139-152 %V 49 %N 2 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita/2015003/ %R 10.1051/ita/2015003 %G en %F ITA_2015__49_2_139_0
Krug, Sacha. Towards using the history in online computation with advice. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 49 (2015) no. 2, pp. 139-152. doi : 10.1051/ita/2015003. http://archive.numdam.org/articles/10.1051/ita/2015003/
J. Arndt, Matters Compuational: Ideas, Algorithms, Source Code. Springer (2011). | Zbl
K. Barhum, H.-J. Böckenhauer, M. Forišek, H. Gebauer, J. Hromkovič, S. Krug, J. Smula and B. Steffen, On the power of advice and randomization for the disjoint path allocation problem. In Proc. of SOFSEM. Vol. 8327 of Lect. Note Comput. Sci. Springer (2014) 89–101. | MR
M.P. Bianchi, H.-J. Böckenhauer, J. Hromkovič and L. Keller, Online coloring of bipartite graphs with and without advice. In Proc. of COCOON. Vol. 7434 of Lect. Note Comput. Sci. Springer (2012) 519–530. | MR
H.-J. Böckenhauer, J. Hromkovič, D. Komm, S. Krug, J. Smula and A. Sprock, The string guessing problem as a method to prove lower bounds on the advice complexity. In Proc. of COCOON. Vol. 7936 of Lect. Note Comput. Sci. Springer (2013) 493–504. | MR
H.-J. Böckenhauer, D. Komm, R. Královič and R. Královič, On the advice complexity of the k-server problem. In Proc. of ICALP. Vol. 6755 of Lect. Note Comput. Sci. Springer (2011) 207–218. | MR
H.-J. Böckenhauer, D. Komm, R. Královič, R. Královič and T. Mömke, On the advice complexity of online problems. In Proc. of ISAAC. Vol. 5878 of Lect. Note Comput. Sci. Springer (2009) 331–340. | Zbl
H.-J. Böckenhauer, D. Komm, R. Královič and P. Rossmanith, On the advice complexity of the knapsack problem. In Proc. of LATIN. Vol. 7256 of Lect. Note Comput. Sci. Springer (2012) 61–72. | MR | Zbl
A. Borodin and R. El-Yaniv, Online Computation and Competitive Analysis. Cambridge University Press (1998). | MR | Zbl
G. Cohen, I. Honkala, S. Litsyn and A. Lobstein, Covering Codes. Elsevier Science Publishers Ltd. (1997). | MR | Zbl
S. Dobrev, R. Královič and D. Pardubská, How much information about the future is needed? In Proc. of SOFSEM. Vol. 4910 of Lect. Note Comput. Sci. Springer (2008) 247–258. | Zbl
, , and , Online computation with advice. Theor. Comput. Sci. 412 (2011) 2642–2656. | DOI | MR | Zbl
M. Forišek, L. Keller and M. Steinová, Advice complexity of online coloring for paths. In Proc. of LATA (2012) 228–239. | MR
S. Gupta, S. Kamali and A. López-Ortiz, On advice complexity of the k-server problem under sparse metrics. In Proc. of SIROCCO. Vol. 8179 of Lect. Note Comput. Sci. Springer (2013) 55–67. | MR
G. Kéri, Tables for Bounds on Covering Codes. http://www.sztaki.hu/˜keri/codes/. Accessed: 2014-05-30.
D. Komm, R. Královič and T. Mömke, On the advice complexity of the set cover problem. In Proc. of CSR. Vol. 7353 of Lect. Note Comput. Sci. Springer (2012) 241–252. | MR
F.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes, 2nd edition. North-Holland (1978). | MR | Zbl
M.P. Renault and A. Rosén, On online algorithms with advice for the k-server problem. In Proc. of WAOA (2011) 198–210. | MR | Zbl
S. Seibert, A. Sprock and W. Unger, Advice complexity of the online coloring problem. In Proc. of CIAC. Vol. 7878 of Lect. Note Comput. Sci. Springer (2013) 345–357. | MR
and , Amortized efficiency of list update and paging rules. Commun. ACM 28 (1985) 202–208. | DOI | MR
Cité par Sources :
