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 Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. STOC '03 June 9-11, 2003. San Diego, California, USA. Copyright 2003 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 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.
Our first application, stated in Section 3, deals with an online version of the set cover problem as introduced in REF .
The online set cover problem
STOC '03
Mathematics Computer Science