2003 · 139 citations · 10 references
Natural SciencesComputer ScienceMathematicsCombinatoricsOptimizationSet TheoryApproximation AlgorithmsCombinatorial OptimizationCombinatorial Set TheoryOnline AlgorithmsOnline Set CoverSet CoverSet Cover Problem
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 COPT that covers X'. The performance of the algorithm is the ratio between the cost of C and the cost of COPT. 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 the fractional solution they supply into a deterministic online algorithm.
10
A threshold of ln <i>n</i> for approximating set cover
Uriel Feige · Journal of the ACM · 1998 · 3.1K citations · Full text
A Greedy Heuristic for the Set-Covering Problem
Vašek Chvátal · Mathematics of Operations Research · 1979 · 2.6K citations
The Weighted Majority Algorithm
N. Littlestone, Manfred K. Warmuth · Information and Computation · 1994 · 2K citations
On the ratio of optimal integral and fractional covers
László Lovász · Discrete Mathematics · 1975 · 1.1K citations