Approximation Algorithms for Partial Covering Problems

View/ Open
Date
2001-05-10Author
Gandhi, Rajiv
Khuller, Samir
Srinivasan, Aravind
Metadata
Show full item recordAbstract
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 R^d by disks.
(Cross-referenced as UMIACS-TR-2001-23)