A New Approximation Algorithm for k-Set Cover Problem

Autor: Salwa M. Ali, Hanaa A. E. Essa, Soheir M. Khamis, Yasser M. Abd El-Latif
Rok vydání: 2015
Předmět:
Zdroj: Arabian Journal for Science and Engineering. 41:935-940
ISSN: 2191-4281
1319-8025
DOI: 10.1007/s13369-015-1895-3
Popis: In the set cover problem (SCP), a set of elements \({X = \{x_{1}, x_{2}, \ldots, x_{n}\}}\) and a collection \({F = \{S_{1}, S_{2}, \ldots, S_{m}\}}\) of subsets of X, for some integers \({n, m \geq 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 \subseteq F}\) such that \({\bigcup\nolimits_{S\in C} S = X}\) and C has the minimum cardinality. When \({|S| \leq k}\) for all \({S \in F}\), the k-set cover problem (k-SCP) is obtained. For all \({k \geq 3}\), 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 \({h_{k}}\)-approximation algorithm, where \({h_{k} = \sum\nolimits_{i=1}^k {\frac{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 + \frac{1}{k})}\)-algorithm with a polynomial running time for \({k \geq 6}\) that improves the previous best approximation ratio \({h_{k} - 0.5902}\) for all values of \({k \geq 6}\).
Databáze: OpenAIRE
Externí odkaz: