Activities per year
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 (1 + (c1) ^{c1}/c ^{c} n = Θ(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 easytouse 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 Θ(n/c). Our results improve on this by providing an exact formula for the higherorder term. Böckenhauer et al. (ISAAC 2009) gave a lower bound of Ω(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.
Original language  English 

Title of host publication  32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) 
Editors  Ernst W. Mayr, Nicolas Ollinger 
Volume  30 
Publisher  Schloss DagstuhlLeibnizZentrum fuer Informatik 
Publication date  2015 
Pages  116129 
ISBN (Electronic)  9783939897781 
DOIs  
Publication status  Published  2015 
Event  32nd International Symposium on Theoretical Aspects of Computer Science  Technische Universität München, Garching, Germany Duration: 4. Mar 2015 → 7. Mar 2015 
Conference
Conference  32nd International Symposium on Theoretical Aspects of Computer Science 

Location  Technische Universität München 
Country/Territory  Germany 
City  Garching 
Period  04/03/2015 → 07/03/2015 
Series  Leibniz International Proceedings in Informatics 

Volume  30 
ISSN  18688969 
Keywords
 Advice complexity
 Advice complexity class AOC
 Asymmetric string guessing
 Covering designs
 Online algorithms
Related Activities

International Symposium on Theoretical Aspects of Computer Science
Joan Boyar (Participant)
4. Mar 2015 → 7. Mar 2015Activity: Attending an event › Organisation or participation in workshops, courses or seminars

International Symposium on Theoretical Aspects of Computer Science
Christian Kudahl (Participant)
4. Mar 2015 → 7. Mar 2015Activity: Attending an event › Conference organisation or participation