primal-dual based distributed algorithms for vertex cover with semi-hard capacities
In this paper we consider the weighted, capacitated vertex cover problem with hard capacities (capVC). Here, we are given an undirected graph G=(V,E) , non-negative vertex weights wt v for all vertices v ? V , and node-capacities B v ? 1 for all v ? V . A feasible solution to a given capVC instance consists of a vertex cover C ? V . Each edge e ? E is assigned to one of its endpoints in C and the number of edges assigned to any vertex v ? C is at most B v . The goal is to minimize the total weight of C .For a parameter ?>0 we give a deterministic, distributed algorithm for the capVC problem that computes a vertex cover C of weight at most (2+?)  opt where opt is the weight of a minimum-weight feasible solution to the given instance. The number of edges assigned to any node v ? C is at most (4+?) B v . The running time of our algorithm is O(log (n W)/?) , where n is the number of nodes in the network and W=wt max /weight min is the ratio of largest to smallest weight.This result is complemented by a lower-bound saying that any distributed algorithm for capVC which requires a poly-logarithmic number of rounds is bound to violate the capacity constraints by a factor two.The main feature of the algorithm is that it is derived in a systematic fashion starting from a primal-dual sequential algorithm.
distributed algorithms vertex cover primal-dual algorithms approximation algorithms