Abstract | ||
---|---|---|
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 wtv for all vertices v ∈ V, and node-capacities Bv ≥ 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 Bv. 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+ε)• Bv. The running time of our algorithm is O(log (n W)/ε), where n is the number of nodes in the network and W=wtmax/weightmin 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. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1145/1073814.1073835 | PODC |
Keywords | Field | DocType |
capvc problem,poly-logarithmic number,primal-dual sequential algorithm,capacitated vertex cover problem,smallest weight,total weight,capvc instance,non-negative vertex weights wtv,semi-hard capacity,node v,vertex v,distributed algorithm,vertex cover,distributed algorithms,approximation algorithms,lower bound | Approximation algorithm,Graph,Discrete mathematics,Combinatorics,Vertex (geometry),Vertex (graph theory),Neighbourhood (graph theory),Distributed algorithm,Vertex cover,Sequential algorithm,Mathematics | Conference |
ISBN | Citations | PageRank |
1-58113-994-2 | 12 | 0.64 |
References | Authors | |
18 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
F. Grandoni | 1 | 12 | 0.64 |
Jochen Könemann | 2 | 158 | 9.98 |
A. Panconesi | 3 | 23 | 1.28 |
Mauro Sozio | 4 | 620 | 31.39 |