Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952008 | Theoretical Computer Science | 2017 | 12 Pages |
Abstract
We study the advice complexity of an online version of the set cover problem. The goal is to quantify the information that online algorithms for this problem need to be supplied with to compute high-quality solutions and to overcome the drawback of not knowing future requests. This concept was successfully applied to many prominent online problems in the past while trying to capture the essence of “what makes an online problem hard.” The online set cover problem was introduced by Alon et al. (2009) [2]: for a ground set of size n and a set family of m subsets of the ground set, we obtain bounds in both n and m. We show that a linear number (with respect to both n and m) of advice bits is both sufficient and necessary to perform optimally. Furthermore, we prove that O((nlogâ¡c)/c) bits are sufficient to design a c-competitive online algorithm, and this bound is tight up to a factor of O(logâ¡c). We further give upper and lower bounds for achieving c-competitiveness with respect to m. Finally, we analyze the advice complexity of the problem with respect to some natural parameters, i.e., measurable properties of the inputs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Stefan Dobrev, Jeff Edmonds, Dennis Komm, Rastislav KráloviÄ, Richard KráloviÄ, Sacha Krug, Tobias Mömke,