A New Approximation Algorithm for k-Set Cover Problem

摘要

In the set cover problem (SCP), a set of elements X = {x1, x2, . . . , xn} and a collection F = {S1, S2, . . . , Sm} of subsets of X, for some integers n,m ≥ 1, are given. In addition, each element of X belongs to at least one member of F. The problem is to find a sub-collection C ⊆ F such that ∪_(S∈C) S = X and C has the minimum cardinality. When |S| ≤ k for all S ∈ F, the k-set cover problem (k- SCP) is obtained. For all k ≥ 3, the k-SCP is an NP-complete optimization problem (Karp inComplexity of computer computations. Plenum Press, New-York, pp 85-103, 1972). It is well known that a greedy algorithm for the k-SCP is a h_k - approximation algorithm, where h_k = ∑_(i=1)~k 1/i is the k~(th) harmonic number. Since the SCP is a fundamental problem, so there is a research effort to improve this approximation ratio. In this paper, the authors propose an approximation algorithm which accepts any instance of the k-SCP problem as an input. This approximation algorithm is a (1 + 1/k )- algorithm with a polynomial running time for k ≥ 6 that improves the previous best approximation ratio h_k −0.5902 for all values of k ≥ 6.