A New Approximation Algorithm for k-Set Cover Problem

作者：Essa Hanaa A E; Abd El Latif Yasser M^*; Ali Salwa M; Khamis Soheir M

来源：ARABIAN JOURNAL FOR SCIENCE AND ENGINEERING, 2016, 41(3): 935-940.

DOI：10.1007/s13369-015-1895-3

• Set cover problem (SCP)
• An approximation algorithm
• A greedy algorithm
• An NP-complete optimization problem

In the set cover problem (SCP), a set of elements and a collection of subsets of X, for some integers , are given. In addition, each element of belongs to at least one member of F. The problem is to find a sub-collection such that and C has the minimum cardinality. When for all , the k-set cover problem (k-SCP) is obtained. For all , the k-SCP is an NP-complete optimization problem (Karp in Complexity 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 -approximation algorithm, where is the 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 -algorithm with a polynomial running time for that improves the previous best approximation ratio for all values of .

• 出版日期2016-3