article · 2008

The Online Set Cover Problem (Extended Abstract)

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

Cited by 0Abstract and details only

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 cS 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 (off-line) a family of sets COP T that covers X ′. The performance of the algorithm is the ratio between the cost of C and the cost of COP T. 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 estab-

Cite this paper

APA 7

Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., & Naor, J. S. (2008). The Online Set Cover Problem (Extended Abstract).

MLA 9

Alon, Noga, et al. “The Online Set Cover Problem (Extended Abstract).” 2008.

Chicago

Alon, Noga, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph (seffi Naor. 2008. “The Online Set Cover Problem (Extended Abstract).”

Harvard

Alon, N. et al. (2008) ‘The Online Set Cover Problem (Extended Abstract)’.

BibTeX

@article{alon2008online,
  title = {{The Online Set Cover Problem (Extended Abstract)}},
  author = {Alon, Noga and Awerbuch, Baruch and Azar, Yossi and Buchbinder, Niv and Naor, Joseph (seffi},
  year = {2008}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.