Unweighted Set-Covering (The Set-Covering Problem)
Jump to navigation
Jump to search
Description
Given a universe $U$, i.e. a set of elements $\{1, 2, \ldots, n\}$, and a collection $S$ of $m$ sets whose union is the universe, identify the smallest sub-collection of $S$ whose union is the universe.
Related Problems
Generalizations: Weighted Set-Covering
Parameters
$U$: the universe of elements to be covered
$S$: the collection of sets
$n$: number of elements in the universe
$m$: number of sets in the collection
$H(x)$: the $x^{th}$ Harmonic number
Table of Algorithms
Name | Year | Time | Space | Approximation Factor | Model | Reference |
---|---|---|---|---|---|---|
Alon; Moshkovitz & Safra | 2006 | $O(nlogn)$ | Deterministic | Time | ||
Integer linear program Vazirani | 2001 | $O(n^{2})$ | $O(U)$ | \log n | Deterministic | Time |
Greedy Algorithm | 1996 | $O(n^{3} \log n)$ | $O(U)$ | \ln(n) - \ln(\ln(n)) + \Theta(1) | Deterministic | Time |
Lund & Yannakakis | 1994 | $O({2}^n)$ | Exact | Deterministic | Time | |
Feige | 1998 | $O({2}^n)$ | Exact | Deterministic | Time | |
Raz & Safra | 1997 | $O(n^{3} \log^{3} n)$ | Exact | Deterministic | Time | |
Dinur & Steurer | 2013 | $O(n^{2} \log n)$ | Exact | Deterministic | Time | |
Cardoso; Nuno; Abreu; Rui | 2014 | $O(n^{2})$ | Exact | Parallel | Time | |
Brute force | 1972 | $O(U {2}^n)$ | $O(U)$ | Exact | Deterministic |