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 = {e_1, e_2, ..., e_n} and a collection F of subsets of E. The problem is to compute a subcollection SOL is contained in F such that ∪_(s_j ∈ SOL) S_j = E and its size |SOL| is minimized. When |S| ≤ k for all S ∈ 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 = Σ~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 modifications 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/309)-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.