Approximating the dense set-cover problem

摘要

We study the set-cover problem, i.e. given a collection C of subsets of a finite set U, find a minimum size subset C′⊆C such that every element in U belongs to at least one member of C. An instance (C,U) of the set-cover problem is k-bounded if the number of occurrences in C of any element is bounded by a constant k⩾2.We present an approximation algorithm for the k-bounded set-cover problem, that achieves the ratio kk−(k−1)1−εk+o(1), where ε is defined as |U|/(|C|k). If ε is relatively high, we say that the problem is dense, and this ratio in this case is better than k, which is the best known constant ratio for this problem. In the case that the number of occurrences in C of any element is exactly k=2 the problem is known as the vertex-cover problem. For dense graphs, our algorithm achieves an approximation ratio better than that of Nagamochi and Ibaraki (Japan J. Indust. Appl. Math. 16 (1999) 369), and the same approximation ratios as Karpinski and Zelikovsky (Proceedings of DIMACS Workshop on Network Design: Connectivity and Facilities Location, Vol. 40, Princeton, 1998, pp. 169–178). In our algorithm we use a combinatorial property of the set-cover problem, which is based on the classical greedy algorithm for the set-cover problem. We use this property to define a “greedy-sequence”, which is defined over a given instance of the set-cover problem and its cover.In addition, we show evidence that the ratio we achieve for the ε-dense k-bounded set-cover problem is the best constant ratio one can expect. We do this by showing that finding a better constant ratio is as hard as finding a constant ratio better than k for the k-bounded set-cover problem in which the optimal cover is known to be of size at least |C|k. (k is the best known constant ratio for this version of the k-bounded set-cover problem.) We show a similar lower bound for the approximation ratio for the vertex-cover problem in ε-dense graphs.