Approximation algorithms for partial covering problems

Rajiv Gandhi, Samir Khuller*, Aravind Srinivasan

*Corresponding author for this work

Research output: Contribution to journalArticle

130 Scopus citations

Abstract

We study a generalization of covering problems called 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-partial set cover, we wish to choose a minimum number of sets to cover at least k elements. For k-partial 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-partial vertex cover) in polynomial time. Without making any assumption about the number of sets an element is in, 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-partial 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-partial vertex cover on planar graphs, and for covering k points in Rd by disks.

Original languageEnglish (US)
Pages (from-to)55-84
Number of pages30
JournalJournal of Algorithms
Volume53
Issue number1
DOIs
StatePublished - Oct 1 2004

Keywords

  • Approximation algorithms
  • Partial covering
  • Primal-dual methods
  • Randomized rounding
  • Set cover
  • Vertex cover

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Approximation algorithms for partial covering problems'. Together they form a unique fingerprint.

Cite this