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. We determine the advice complexity of hard online problems such as Online Independent Set, Online Vertex Cover and Online Disjoint Path Allocation. These problems are hard since a single wrong answer by the online algorithm can have devastating consequences. We show that log 1 + (c−1) c−1 cc n = Θ(n/c) bits of advice are necessary and sufficient (up to a lower-order term) to achieve a strict competitive ratio of c for each of these problems. This is done by introducing a new string guessing problem related to that of Böckenhauer et al. (Theoretical Computer Science 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. (Theoretical Computer Science 2002) on Online Independent Set, in a related model, implies 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. 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 log c factor. For the remaining problems, no bounds on their advice complexity were previously known.