Paper Info
Title
Linear-work greedy parallel approximate set cover and variants
Abstract
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(log2 m) depth on input with m edges. Using MaNIS, we obtain RNC algorithms that yield a (1+ε)Hn-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 ≤ logO(1) n and a (1.861+ε)-approximation for metric facility location both in essentially the same work bounds as their sequential counterparts.
Year
DOI
Venue
2011
10.1145/1989493.1989497
SPAA
Keywords
Field
DocType
parallel set,min-sum set,parallel greedy approximation algorithm,graph abstraction,rnc algorithm,max cover,graph problem,set cover,greedy parallel approximate set,linear work,work bound,independent set,approximation algorithms,parallel algorithms,randomized algorithm,facility location,parallel algorithm
Approximation algorithm,Discrete mathematics,Set cover problem,Randomized algorithm,Combinatorics,Metric k-center,Parallel algorithm,Manis,Facility location problem,Independent set,Mathematics
Conference
Citations 
PageRank 
References 
23
0.91
15
Authors
3
Name
Order
Citations
PageRank
Guy E. Blelloch12927207.30
Richard Peng252242.64
Kanat Tangwongsan335720.05