Change search
ReferencesLink to record
Permanent link

Direct link
On the advice complexity of the set cover problem
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
2012 (English)In: Computer Science - Theory and Applications, Springer Berlin/Heidelberg, 2012, Vol. 7353 LNCS, 241-252 p.Conference paper (Refereed)
Abstract [en]

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. 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 a linear number of advice bits is 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.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2012. Vol. 7353 LNCS, 241-252 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 7353
Keyword [en]
Advice complexity, Constant factors, High-quality solutions, Lower and upper bounds, On-line algorithms, Online computations, Online problems, Online versions, Set cover problem, Algorithms, Competition, Computation theory
National Category
Computer Science
URN: urn:nbn:se:kth:diva-103660DOI: 10.1007/978-3-642-30642-6_23ScopusID: 2-s2.0-84865559124ISBN: 978-364230641-9OAI: diva2:561291
7th International Computer Science Symposium in Russia on Computer Science - Theory and Applications, CSR 2012; Nizhny Novgorod;3 July 2012 through 7 July 2012

QC 20121018

Available from: 2012-10-18 Created: 2012-10-17 Last updated: 2012-10-18Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Mömke, Tobias
By organisation
Theoretical Computer Science, TCS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 49 hits
ReferencesLink to record
Permanent link

Direct link