The Library
New and improved bounds for the minimum set cover problem
Tools
Tools
Tools
Saket, Rishi and Sviridenko, Maxim (2012) New and improved bounds for the minimum set cover problem. In: Gupta , Anupam and Jansen , Klaus and Rolim , José and Servedio , Rocco , (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques : 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings. Lecture Notes in Computer Science, Volume 7408 . Berlin Heidelberg: Springer Netherlands, pp. 288-300. ISBN 9783642325113
Research output not available from this repository, contact author.
Official URL: http://dx.doi.org/10.1007/978-3-642-32512-0_25
Abstract
We study the relationship between the approximation factor for the Set-Cover problem and the parameters Δ : the maximum cardinality of any subset, and k : the maximum number of subsets containing any element of the ground set. We show an LP rounding based approximation of (k−1)(1−e−lnΔk−1)+1 , which is substantially better than the classical algorithms in the range k ≈ ln Δ, and also improves on related previous works [19,22]. For the interesting case when k = θ(logΔ) we also exhibit an integrality gap which essentially matches our approximation algorithm. We also prove a hardness of approximation factor of Ω(logΔ(loglogΔ)2) when k = θ(logΔ). This is the first study of the hardness factor specifically for this range of k and Δ, and improves on the only other such result implicitly proved in [18].
| Item Type: | Book Item | ||||
|---|---|---|---|---|---|
| Divisions: | Faculty of Science > Computer Science | ||||
| Series Name: | Lecture Notes in Computer Science | ||||
| Publisher: | Springer Netherlands | ||||
| Place of Publication: | Berlin Heidelberg | ||||
| ISBN: | 9783642325113 | ||||
| ISSN: | 0302-9743 | ||||
| Book Title: | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques : 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings | ||||
| Editor: | Gupta , Anupam and Jansen , Klaus and Rolim , José and Servedio , Rocco | ||||
| Official Date: | 2012 | ||||
| Dates: |
|
||||
| Volume: | Volume 7408 | ||||
| Page Range: | pp. 288-300 | ||||
| DOI: | 10.1007/978-3-642-32512-0_25 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Description: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
