An improved approximation algorithm for vertex cover with hard capacities (extended abstract)

Rajiv Gandhi*, Eran Halperin, Samir Khuller, Guy Kortsarz, Aravind Srinivasan

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

16 Scopus citations

Abstract

In this paper we study the capacitated vertex cover problem, a generalization of the well-known vertex cover problem. Given a graph G = (V, E), the goal is to cover all the edges by picking a minimum cover using the vertices. When we pick a vertex, we can cover up to a pre-specified number of edges incident on this vertex (its capacity). The problem is clearly NP-hard as it generalizes the well-known vertex cover problem. Previously, 2-approximation algorithms were developed with the assumption that multiple copies of a vertex may be chosen in the cover. If we are allowed to pick at most a given number of copies of each vertex, then the problem is significantly harder to solve. Chuzhoy and Naor (Proc. IEEE Symposium on Foundations of Computer Science, 481-489, 2002) have recently shown that the weighted version of this problem is at least as hard as set cover; they have also developed a 3-approximation algorithm for the unweighted version. We give a 2-approximation algorithm for the unweighted version, improving the Chuzhoy-Naor bound of 3 and matching (up to lower-order terms) the best approximation ratio known for the vertex cover problem.

Original languageEnglish (US)
Pages (from-to)164-175
Number of pages12
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2719
StatePublished - Dec 1 2003

Keywords

  • Approximation algorithms
  • Capacitated covering
  • Linear programming
  • Randomized rounding
  • Set cover
  • Vertex cover

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'An improved approximation algorithm for vertex cover with hard capacities (extended abstract)'. Together they form a unique fingerprint.

Cite this