MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

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
Conference URL::
Downloading URL:
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
Note, Abstract, ©
(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
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Julian Mestre		Created
01/15/2008 17:35:35
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