The Library
New and improved bounds for the minimum set cover problem
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.
Request-a-Copy directly from author or use local Library Get it For Me service.
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, Engineering and Medicine > 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 |