MPI-INF D1 Publications: Proceedings Article: Approximation of Partial Capacitated Vertex Cover

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

Options:

Goto entry point

Author, Editor

Author(s):

Bar-Yehuda, Reuven
Flysher, Guy
Mestre, Julián
Rawitz, Dror

dblp
dblp
dblp
dblp

Not MPG Author(s):

Bar-Yehuda, Reuven
Flysher, Guy
Rawitz, Dror

Editor(s):

Arge, Lars
Hoffmann, Michael
Welzl, Emo

dblp
dblp
dblp

Not MPII Editor(s):

Arge, Lars
Hoffmann, Michael
Welzl, Emo

BibTeX cite key*:

conf/esa/Bar-YehudaFMR2007

Title, Booktitle

Title*:	Approximation of Partial Capacitated Vertex Cover
Booktitle*:	15th Annual European Symposium on Algorithms

Event, URLs

URL of the conference:
URL for downloading the paper:
Event Address*:	Eilat, Israel	Language:	English
Event Date* (no longer used):		Organization:
Event Start Date:	8 October 2007	Event End Date:	10 October 2007

Publisher

Name*:	Springer	URL:
Address*:	Berlin / Heidelberg	Type:

Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:	4698	Number:
Month:		Pages:	335-346
Year*:	2007	VG Wort Pages:
ISBN/ISSN:	978-3-540-75519-7	Sequence Number:
DOI:	10.1007/978-3-540-75520-3_31


(LaTeX) Abstract:	We study the \emph{partial capacitated vertex cover problem} (PCVC) in which the input consists of a graph $G$ and a covering requirement $L$. Each edge $e$ in $G$ is associated with a \emph{demand} (or \emph{load}) $\ell(e)$, and each vertex $v$ is associated with a (soft) \emph{capacity} $c(v)$ and a \emph{weight} $w(v)$. A feasible solution is an assignment of edges to vertices such that the total demand of assigned edges is at least $L$. The weight of a solution is $\sum_v \alpha(v) w(v)$, where $\alpha(v)$ is the number of copies of $v$ required to cover the demand of the edges that are assigned to $v$. The goal is to find a solution of minimum weight. We consider three variants of PCVC. In PCVC with \emph{separable demands} the only requirement is that total demand of edges assigned to $v$ is at most $\alpha(v) c(v)$. In \pcvc\ with \emph{inseparable demands} there is an additional requirement that if an edge is assigned to $v$ then it must be assigned to one of its copies. The third variant is the unit demands version. We present $3$-approximation algorithms for both PCVC with separable demands and PCVC with inseparable demands. We also present a $2$-approximation algorithm for PCVC with unit demands. We show that similar results can be obtained for PCVC in hypergraphs and for the \emph{prize collecting} version of capacitated vertex cover. Our algorithms are based on a unified approach for designing and analyzing approximation algorithms for capacitated covering problems. This approach yields simple algorithms whose analyses rely on the local ratio technique and sophisticated charging schemes.
Keywords:	Approximation Algorithms, Covering Problems


Download Access Level:	Public

Correlation

MPG Unit:	Max-Planck-Institut für Informatik

MPG Subunit:	Algorithms and Complexity Group
Audience:	experts only
Appearance:	MPII WWW Server, MPII FTP Server, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{conf/esa/Bar-YehudaFMR2007,
AUTHOR = {Bar-Yehuda, Reuven and Flysher, Guy and Mestre, Juli{\'a}n and Rawitz, Dror},
EDITOR = {Arge, Lars and Hoffmann, Michael and Welzl, Emo},
TITLE = {Approximation of Partial Capacitated Vertex Cover},
BOOKTITLE = {15th Annual European Symposium on Algorithms},
PUBLISHER = {Springer},
YEAR = {2007},
VOLUME = {4698},
PAGES = {335--346},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Eilat, Israel},
ISBN = {978-3-540-75519-7},
DOI = {10.1007/978-3-540-75520-3_31},
}

Entry last modified by Julian Mestre, 02/16/2009

Edit History (please click the blue arrow to see the details)

	Editor(s) Julian Mestre	Created 01/15/2008 05:35:35 PM
Revisions 7. 6. 5. 4. 3.	Editor(s) Julian Mestre Julian Mestre Julian Mestre Julian Mestre Julian Mestre	Edit Dates 02/16/2009 09:35:11 AM 02/07/2009 10:39:04 AM 06/04/2008 03:07:08 PM 06/04/2008 03:04:50 PM 06/04/2008 03:00:02 PM

Attachment Section