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