@inproceedings{d67d7fdeeef043b5ac558e745f9a3366,

title = "Approximation algorithms for partial covering problems extended abstract",

abstract = "We study the generalization of covering problems to partial covering. Here we wish to cover only a desired number of elements, rather than covering all elements as in standard covering problems. For example, in k-set cover, we wish to choose a minimum number of sets to cover at least k elements. For k-set cover, if each element occurs in at most f sets, then we derive a primal-dual f-approximation algorithm (thus implying a 2-approximation for k-vertex cover) in polynomial time. In addition to its simplicity, this algorithm has the advantage of being parallelizable. For instances where each set has cardinality at most three, we obtain an approximation of 4/3. We also present better-than-2-approximation algorithms for k-vertex cover on bounded degree graphs, and for vertex cover on expanders of bounded average degree. We obtain a polynomial-time approximation scheme for k-vertex cover on planar graphs, and for covering points in Rd by disks.",

keywords = "Approximation algorithms, Primal-dual methods, Prtial covering, Randomized rounding, St cover, Vertex cover",

author = "Rajiv Gandhi and Samir Khuller and Aravind Srinivasan",

year = "2001",

doi = "10.1007/3-540-48224-5_19",

language = "English (US)",

isbn = "3540422870",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "225--236",

editor = "Fernando Orejas and Spirakis, {Paul G.} and {van Leeuwen}, Jan",

booktitle = "Automata, Languages and Programming - 28th International Colloquium, ICALP 2001, Proceedings",

note = "28th International Colloquium on Automata, Languages and Programming, ICALP 2001 ; Conference date: 08-07-2001 Through 12-07-2001",

}