Capacitated vertex covering with applications

Sudipto Guha, Refael Hassin, Samir Khuller, Einat Or

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

20 Scopus citations


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 upto a pre-specified number of edges incident on this vertex (its capacity). The problem is NP-hard. We give a primal-dual based 2 approximation and study several generalizations, as well as the problem restricted to trees.

Original languageEnglish (US)
Title of host publicationProceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
PublisherAssociation for Computing Machinery
Number of pages8
ISBN (Electronic)089871513X
StatePublished - Jan 1 2002
Event13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 - San Francisco, United States
Duration: Jan 6 2002Jan 8 2002

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


Conference13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
Country/TerritoryUnited States
CitySan Francisco

ASJC Scopus subject areas

  • Software
  • Mathematics(all)


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

Cite this