Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

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

Action:

login to update

Options:








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



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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section