Journal
SIAM JOURNAL ON COMPUTING
Volume 38, Issue 3, Pages 825-840Publisher
SIAM PUBLICATIONS
DOI: 10.1137/06065310X
Keywords
vertex cover; approximation algorithms; distributed algorithms; primal-dual algorithms
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available