Approximation Algorithms for Partial Covering Problems
Approximation Algorithms for Partial Covering Problems
Loading...
Files
Publication or External Link
Date
2001-05-10
Authors
Gandhi, Rajiv
Khuller, Samir
Srinivasan, Aravind
Advisor
Citation
DRUM DOI
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 R^d by disks.
(Cross-referenced as UMIACS-TR-2001-23)