APPROXIMATING THE UNWEIGHTED k-SET COVER PROBLEM: GREEDY MEETS LOCAL SEARCH

In the unweighted set cover problem we are given a set of elements E = {e1, e2, ..., en} and a collection F of subsets of E. The problem is to compute a subcollection SOL subset of F such that boolean OR(Sj is an element of SOL) S(j) = E and its size vertical bar SOL vertical bar is minimized. When vertical bar S vertical bar <= k for all S is an element of F, we obtain the unweighted k-set cover problem. It is well known that the greedy algorithm is an H(k)-approximation algorithm for the unweighted k-set cover, where H(k) = Sigma(k)(i=1) 1/i is the kth harmonic number and that this bound on the approximation ratio of the greedy algorithm is tight for all constant values of k. Since the set cover problem is a fundamental problem, there is an ongoing research effort to improve this approximation ratio using modi. cations of the greedy algorithm. The previous best improvement of the greedy algorithm is an (H(k) - 1/2)-approximation algorithm. In this paper we present a new (H(k) - 196/390)- approximation algorithm for k >= 4 that improves the previous best approximation ratio for all values of k >= 4. Our algorithm is based on combining a local search during various stages of the greedy algorithm.