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 2-approximation algorithm taking O(log n) rounds and the first parallel 2-approximation 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 \(\delta\)-approximation algorithm taking O(log2 |C|) rounds, where |C| is the number of constraints. (Special cases include CMIP, facility location, and probabilistic (two-stage) 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.