Approximation of Partial Capacitated Vertex Cover
| Autor: | Dror Rawitz, Julián Mestre, Guy Flysher, Reuven Bar-Yehuda |
|---|---|
| Rok vydání: | 2010 |
| Předmět: | |
| Zdroj: | SIAM Journal on Discrete Mathematics. 24:1441-1469 |
| ISSN: | 1095-7146 0895-4801 |
| DOI: | 10.1137/080728044 |
| Popis: | We study the 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 demand (or load) $\ell(e)$, and each vertex $v$ is associated with a (soft) capacity $c(v)$ and a 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 separable demands the only requirement is that the total demand of edges assigned to $v$ is at most $\alpha(v)c(v)$. In PCVC with 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 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|