Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

Request Changes to record.

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:
DateEvent
2012Published
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 View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us