On the Advice Complexity of the Set Cover Problem
OPEN ACCESS
Author / Producer
Date
2011
Publication Type
Report
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
Recently, a new approach to get a deeper understanding of online computation has been introduced: the study of the advice complexity of online problems. The idea is to measure the information that online algorithms need to be supplied with to compute high-quality solutions and to overcome the drawback of not knowing future input requests. This concept was
successfully applied to many prominent online problems including paging, the k-server problem, metrical task systems, or job shop scheduling. In this paper, we study the advice complexity of an online version of the well-known set cover problem introduced by Alon et al.: 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 prove that n bits of advice are both sufficient and necessary to perform optimally. Furthermore, for any constant c, we prove that n − c bits are enough to construct a c-competitive online algorithm and this bound is tight up to a constant factor (only depending on c). Moreover, we show that a linear number of advice bits is both necessary and sufficient to be optimal with respect to m, as well. We further show lower and upper bounds for achieving c-competitiveness also in m.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
738
Pages / Article No.
Publisher
ETH Zurich, Department of Computer Science
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
02150 - Dep. Informatik / Dep. of Computer Science