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 (...
详细信息
ISBN:
(纸本)9781450307437
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 + epsilon)H-n-approximation for set cover, a (1 - 1/e - epsilon)-approximation for max cover and a (4 + epsilon)-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 + epsilon)-approximation for metric facility location both in essentially the same work bounds as their sequential counterparts.
暂无评论