Name
Abstract | ||
|---|---|---|
In this paper we consider the capacitated vertex cover problem, which is the variant of vertex cover where each node is allowed to cover a limited number of edges. We present an efficient, deterministic, distributed approximation algorithm for the problem. Our algorithm computes a $(2+\epsilon)$-approximate solution which violates the capacity constraints by a factor of $(4+\epsilon)$ in a polylogarithmic number of communication rounds. On the other hand, we also show that every efficient distributed approximation algorithm for this problem must violate the capacity constraints. Our result is achieved in two steps. We first develop a $2$-approximate, sequential primal-dual algorithm that violates the capacity constraints by a factor of $2$. Subsequently, we present a distributed version of this algorithm. We demonstrate that the sequential algorithm has an inherent need for synchronization which forces any naive distributed implementation to use a linear number of communication rounds. The challenge in this step is therefore to achieve a reduction of the communication complexity to a polylogarithmic number of rounds without worsening the approximation guarantee. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1137/06065310X | SIAM J. Comput. |
Keywords | Field | DocType |
polylogarithmic number,communication round,capacitated vertex cover,approximation algorithm,primal-dual bicriteria,capacity constraint,primal-dual algorithms,distributed algorithms,vertex cover,capacitated vertex cover problem,approximation algorithms,approximation guarantee,sequential algorithm,sequential primal-dual algorithm,limited number,linear number,communication complexity,distributed algorithm | Discrete mathematics,Approximation algorithm,Combinatorics,Synchronization,Vertex (geometry),Communication complexity,Sequential method,Distributed algorithm,Vertex cover,Sequential algorithm,Mathematics | Journal |
Volume | Issue | ISSN |
38 | 3 | 0097-5397 |
Citations | PageRank | References |
11 | 0.64 | 23 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| F. Grandoni | 1 | 11 | 0.64 |
| Jochen Könemann | 2 | 158 | 9.98 |
| A. Panconesi | 3 | 23 | 1.28 |
| Mauro Sozio | 4 | 620 | 31.39 |