Parallel Set Cover and Hypergraph Matching via Uniform Random Sampling
Parallel Set Cover and Hypergraph Matching via Uniform Random Sampling
The SetCover problem has been extensively studied in many different models of computation, including parallel and distributed settings. From an approximation point of view, there are two standard guarantees: an $O(\log \Delta)$-approximation (where $\Delta$ is the maximum set size) and an $O(f)$-approximation (where $f$ is the maximum number of sets …