neal young / Koufogiannakis09Distributed

The paper presents distributed and parallel δapproximation algorithms for covering problems, where δ is the maximum number of variables on which any constraint depends (for example, δ=2 for vertex cover).
Specific results include the following. For weighted vertex cover, the first distributed 2approximation algorithm taking O(log n) rounds and the first parallel 2approximation algorithm in RNC. The algorithms generalize to covering mixed integer linear programs (CMIP) with two variables per constraint (δ=2).
 For any covering problem with monotone constraints and submodular cost, a distributed $δ$approximation algorithm taking O(log^{2} C) rounds, where C is the number of constraints. (Special cases include CMIP, facility location, and probabilistic (twostage) variants of these problems.)
(This paper gives distributed implementations of algorithms from Greedy δapproximation algorithm for covering with arbitrary constraints and submodular cost .)Conference version of part of Distributed algorithms for covering, packing and maximum weighted matching.
© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.