Capacitated vertex covering with applications

Sudipto Guha; Refael Hassin; Samir Khuller; Einat Or

Capacitated vertex covering with applications

Sudipto Guha, Refael Hassin, Samir Khuller, Einat Or

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

20 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 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 language	English (US)
Title of host publication	Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
Publisher	Association for Computing Machinery
Pages	858-865
Number of pages	8
ISBN (Electronic)	089871513X
State	Published - Jan 1 2002
Event	13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 - San Francisco, United States Duration: Jan 6 2002 → Jan 8 2002

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume	06-08-January-2002

Conference

Conference	13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
Country	United States
City	San Francisco
Period	1/6/02 → 1/8/02

ASJC Scopus subject areas

Software
Mathematics(all)

Access to Document

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

Cite this

@inproceedings{1ca4ce5de14949d3b56b66d8c3c73636,

title = "Capacitated vertex covering with applications",

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 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.",

author = "Sudipto Guha and Refael Hassin and Samir Khuller and Einat Or",

year = "2002",

month = jan,

day = "1",

language = "English (US)",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

pages = "858--865",

booktitle = "Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002",

note = "13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 ; Conference date: 06-01-2002 Through 08-01-2002",

}

Guha, S, Hassin, R, Khuller, S & Or, E 2002, Capacitated vertex covering with applications. in Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 06-08-January-2002, Association for Computing Machinery, pp. 858-865, 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002, San Francisco, United States, 1/6/02.

Capacitated vertex covering with applications. / Guha, Sudipto; Hassin, Refael; Khuller, Samir; Or, Einat.

Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002. Association for Computing Machinery, 2002. p. 858-865 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 06-08-January-2002).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Capacitated vertex covering with applications

AU - Guha, Sudipto

AU - Hassin, Refael

AU - Khuller, Samir

AU - Or, Einat

PY - 2002/1/1

Y1 - 2002/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84902074040&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84902074040&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84902074040

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 858

EP - 865

BT - Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002

PB - Association for Computing Machinery

T2 - 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002

Y2 - 6 January 2002 through 8 January 2002

ER -