Approximation algorithms for partial covering problems extended abstract

Rajiv Gandhi, Samir Khuller, Aravind Srinivasan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

25 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 28th International Colloquium, ICALP 2001, Proceedings
EditorsFernando Orejas, Paul G. Spirakis, Jan van Leeuwen
PublisherSpringer Verlag
Pages225-236
Number of pages12
ISBN (Print)3540422870, 9783540422877
DOIs
StatePublished - 2001
Event28th International Colloquium on Automata, Languages and Programming, ICALP 2001 - Crete, Greece
Duration: Jul 8 2001Jul 12 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2076 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference28th International Colloquium on Automata, Languages and Programming, ICALP 2001
CountryGreece
CityCrete
Period7/8/017/12/01

Keywords

  • Approximation algorithms
  • Primal-dual methods
  • Prtial covering
  • Randomized rounding
  • St cover
  • Vertex cover

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

Cite this