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: 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},