Linear-Work Greedy Parallel Approximate Set Cover and Variants

摘要

We present parallel greedy approximation algorithms for set cover and related problems. These algorithms build on an algorithm for solving a graph problem we formulate and study called Maximal Nearly Independent Set (MaNIS)-a graph abstraction of a key component in existing work on parallel set cover. We derive a randomized algorithm for MaNIS that has O(m) work and O(log~2 m) depth on input with m edges. Using MaNIS, we obtain RNC algorithms that yield a (1 + ε)H_n-approximation for set cover, a (1- 1/e-ε)-approximation for max cover and a (4 + ε)-approximation for min-sum set cover all in linear work; and an O(log* n)-approximation for asymmetric k-center for k ≤ log~(O(1)) n and a (1.861 + ≤ε)-approximation for metric facility location both in essentially the same work bounds as their sequential counterparts.