Capacitated vertex covering

Sudipto Guha, Refael Hassin, Samir Khuller*, Einat Or

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

51 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) with weights on the vertices, the goal is to cover all the edges by picking a cover of minimum weight from the vertices. When we pick a copy of a vertex, we pay the weight of the vertex and cover up to a pre-specified number of edges incident on this vertex (its capacity). The problem is NP-hard. We give a primal-dual based approximation algorithm with an approximation guarantee of 2, and study several generalizations, as well as the problem restricted to trees.

Original languageEnglish (US)
Pages (from-to)257-270
Number of pages14
JournalJournal of Algorithms
Volume48
Issue number1
DOIs
StatePublished - Aug 2003

Keywords

  • Approximation algorithm
  • Capacitated network design
  • Vertex cover

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'Capacitated vertex covering'. Together they form a unique fingerprint.

Cite this