Grandoni, Fabrizio and Könemann, Jochen and Panconesi, Alessandro and Sozio, Mauro (2008) A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover. SIAM Journal on Computing, 38 (3). pp. 825-840. ISSN 0097-5397
Full text not available from this repository.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.
| Item Type: | Scientific journal article, Newspaper article or Magazine article |
|---|---|
| Subjects: | Computer sciences |
| Depositing User: | Fabrizio Grandoni |
| Date Deposited: | 14 Mar 2014 09:04 |
| Last Modified: | 23 May 2016 14:54 |
| URI: | http://repository.supsi.ch/id/eprint/4504 |
Actions (login required)
 |
View Item |