A New Approximation Algorithm for k-Set Cover Problem
Essa H.; El-Latif Y.; Ali S.; Khamis, Soheir;
Abstract
© 2015, King Fahd University of Petroleum & Minerals. In the set cover problem (SCP), a set of elements (Formula presented.) and a collection (Formula presented.) of subsets of X, for some integers (Formula presented.) , are given. In addition, each element of (Formula presented.) belongs to at least one member of F. The problem is to find a sub-collection (Formula presented.) such that (Formula presented.) and C has the minimum cardinality. When (Formula presented.) for all (Formula presented.) , the k-set cover problem (k-SCP) is obtained. For all (Formula presented.) , 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 (Formula presented.) -approximation algorithm, where (Formula presented.) is the (Formula presented.) 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 (Formula presented.) -algorithm with a polynomial running time for (Formula presented.) that improves the previous best approximation ratio (Formula presented.) for all values of (Formula presented.).
Other data
Title | A New Approximation Algorithm for k-Set Cover Problem | Authors | Essa H. ; El-Latif Y. ; Ali S. ; Khamis, Soheir | Keywords | Keywords Set cover problem (SCP) • An approximation algorithm • A greedy algorithm • An NP-complete optimization problem | Issue Date | 3-Nov-2015 | Journal | Arabian Journal for Science and Engineering | DOI | 3 https://api.elsevier.com/content/abstract/scopus_id/84959232754 935 41 10.1007/s13369-015-1895-3 |
Scopus ID | 2-s2.0-84959232754 |
Attached Files
File | Description | Size | Format | |
---|---|---|---|---|
A New Approximation Algorithm.pdf | 1.1 MB | Adobe PDF | View/Open |
Similar Items from Core Recommender Database
Items in Ain Shams Scholar are protected by copyright, with all rights reserved, unless otherwise indicated.