The online set cover problem

Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph Naor

Research output: Contribution to journalArticle

66 Scopus citations

Abstract

Let X = {1,2,..., n} be a ground set of n elements, and let S be a family of subsets of X, |S| = m, with a positive cost c S associated with each S ∈ S. Consider the following online version of the set cover problem, described as a game between an algorithm and an adversary. An adversary gives elements to the algorithm from X one by one. Once a new element is given, the algorithm has to cover it by some set of S containing it. We assume that the elements of X and the members of S are known in advance to the algorithm; however, the set X' ⊆ X of elements given by the adversary is not known in advance to the algorithm. (In general, X' may be a strict subset of X.) The objective is to minimize the total cost of the sets chosen by the algorithm. Let C denote the family of sets in S that the algorithm chooses. At the end of the game the adversary also produces (offline) a family of sets C OPT that covers X'. The performance of the algorithm is the ratio between the cost of C and the cost of C OPT. The maximum ratio, taken over all input sequences, is the competitive ratio of the algorithm. We present an O(log m log n) competitive deterministic algorithm for the problem and establish a nearly matching Ω (log n log m/log log m+log log n) lower bound for all interesting values of m and n. The techniques used are motivated by similar techniques developed in computational learning theory for online prediction (e.g., the WINNOW algorithm) together with a novel way of converting a fractional solution into a deterministic online algorithm.

Original languageEnglish (US)
Pages (from-to)361-370
Number of pages10
JournalSIAM Journal on Computing
Volume39
Issue number2
DOIs
StatePublished - Jul 15 2009
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

  • Competitive factor
  • Online
  • Set cover

Fingerprint Dive into the research topics of 'The online set cover problem'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., & Naor, J. (2009). The online set cover problem. SIAM Journal on Computing, 39(2), 361-370. https://doi.org/10.1137/060661946