The online set cover problem

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 (off-line) 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 the fractional solution they supply into a deterministic online algorithm.

REFERENCES

• 1: N. Alon and J. H. Spencer, The probabilistic method, Second Edition, Wiley, New York, 2000.
• 2: Baruch Awerbuch , Yossi Azar , Amos Fiat , Tom Leighton, Making commitments in the face of uncertainty: how to pick a winner almost every time (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.519-530, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.238000]
• 3: Avrim Blum, On-line Algorithms in Machine Learning, Developments from a June 1996 seminar on Online algorithms: the state of the art, p.306-325, January 1998
• 4: A. Blum, Online learning tools for online algorithms, Dagstuhl Workshop on Online Algorithms, July 2002. (See http://www-2.cs.cmu.edu/~avrim/surveys.html.)
• 5: Avrim Blum , Shuchi Chawla , Adam Kalai, Static optimality and dynamic search-optimality in lists and trees, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.1-8, January 06-08, 2002, San Francisco, California
• 6: V. Chvátal. A greedy heuristic for the set-covering problem. Mathematics of Operations Research, 4(3):233--235, 1979.
• 7: Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
• 8: Yoav Freund , Robert E. Schapire, Game theory, on-line prediction and boosting, Proceedings of the ninth annual conference on Computational learning theory, p.325-332, June 28-July 01, 1996, Desenzano del Garda, Italy [doi>10.1145/238061.238163]
• 9: D. S. Johnson. Approximation algorithms for combinatorial problems. J. Comput. System Sci., 9:256--278, 1974.
• 10: L. Lovász. On the ratio of optimal and fractional covers. Discrete Mathematics, 13:383--390, 1975.
• 11: Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

General Terms:
Algorithms, Theory

Keywords:
competitive analysis, derandomization, on-line algorithms, randomized rounding, set-cover