Linear-work greedy parallel approximate set cover and variants
Guy E. Blelloch, Richard Peng, Kanat Tangwongsan · 2011
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.