Unweighted Set-Covering: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 10: | Line 10: | ||
== Parameters == | == Parameters == | ||
U: the universe of elements to be covered | $U$: the universe of elements to be covered | ||
S: the collection of sets | $S$: the collection of sets | ||
n: number of elements in the universe | $n$: number of elements in the universe | ||
m: number of sets in the collection | $m$: number of sets in the collection | ||
H(x): the | $H(x)$: the $x^{th}$ Harmonic number | ||
== Table of Algorithms == | == Table of Algorithms == | ||
| Line 32: | Line 32: | ||
| [[Integer linear program Vazirani (Unweighted Set-Covering; Weighted Set-Covering The Set-Covering Problem)|Integer linear program Vazirani]] || 2001 || $O(n^{2})$ || $O(U)$ || \log n || Deterministic || [https://link.springer.com/chapter/10.1007/978-3-662-04565-7_13 Time] | | [[Integer linear program Vazirani (Unweighted Set-Covering; Weighted Set-Covering The Set-Covering Problem)|Integer linear program Vazirani]] || 2001 || $O(n^{2})$ || $O(U)$ || \log n || Deterministic || [https://link.springer.com/chapter/10.1007/978-3-662-04565-7_13 Time] | ||
|- | |- | ||
| [[Greedy Algorithm ( The Set-Covering Problem)|Greedy Algorithm]] || 1996 || $O(n^{3} log n)$ || $O(U)$ || \ln(n) - \ln(\ln(n)) + \Theta(1) || Deterministic || [https://dl.acm.org/doi/10.1145/237814.237991 Time] | | [[Greedy Algorithm ( The Set-Covering Problem)|Greedy Algorithm]] || 1996 || $O(n^{3} \log n)$ || $O(U)$ || \ln(n) - \ln(\ln(n)) + \Theta(1) || Deterministic || [https://dl.acm.org/doi/10.1145/237814.237991 Time] | ||
|- | |- | ||
| [[Lund & Yannakakis ( The Set-Covering Problem)|Lund & Yannakakis]] || 1994 || $O({2}^n)$ || || Exact || Deterministic || [https://doi.org/10.1145%2F185675.306789 Time] | | [[Lund & Yannakakis ( The Set-Covering Problem)|Lund & Yannakakis]] || 1994 || $O({2}^n)$ || || Exact || Deterministic || [https://doi.org/10.1145%2F185675.306789 Time] | ||
| Line 38: | Line 38: | ||
| [[Feige ( The Set-Covering Problem)|Feige]] || 1998 || $O({2}^n)$ || || Exact || Deterministic || [https://courses.cs.duke.edu/spring07/cps296.2/papers/p634-feige.pdf Time] | | [[Feige ( The Set-Covering Problem)|Feige]] || 1998 || $O({2}^n)$ || || Exact || Deterministic || [https://courses.cs.duke.edu/spring07/cps296.2/papers/p634-feige.pdf Time] | ||
|- | |- | ||
| [[Raz & Safra ( The Set-Covering Problem)|Raz & Safra]] || 1997 || $O(n^{3} log^{3} n)$ || || Exact || Deterministic || [https://dl.acm.org/doi/10.1145/258533.258641 Time] | | [[Raz & Safra ( The Set-Covering Problem)|Raz & Safra]] || 1997 || $O(n^{3} \log^{3} n)$ || || Exact || Deterministic || [https://dl.acm.org/doi/10.1145/258533.258641 Time] | ||
|- | |- | ||
| [[Dinur & Steurer ( The Set-Covering Problem)|Dinur & Steurer]] || 2013 || $O(n^{2} log n)$ || || Exact || Deterministic || [https://www.dsteurer.org/paper/productgames.pdf Time] | | [[Dinur & Steurer ( The Set-Covering Problem)|Dinur & Steurer]] || 2013 || $O(n^{2} \log n)$ || || Exact || Deterministic || [https://www.dsteurer.org/paper/productgames.pdf Time] | ||
|- | |- | ||
| [[Cardoso; Nuno; Abreu; Rui ( The Set-Covering Problem)|Cardoso; Nuno; Abreu; Rui]] || 2014 || $O(n^{2})$ || || Exact || Parallel || [https://www.semanticscholar.org/paper/An-efficient-distributed-algorithm-for-computing-Cardoso-Abreu/ce32696c1176800c5b90fab026bf93f282e2b161 Time] | | [[Cardoso; Nuno; Abreu; Rui ( The Set-Covering Problem)|Cardoso; Nuno; Abreu; Rui]] || 2014 || $O(n^{2})$ || || Exact || Parallel || [https://www.semanticscholar.org/paper/An-efficient-distributed-algorithm-for-computing-Cardoso-Abreu/ce32696c1176800c5b90fab026bf93f282e2b161 Time] | ||
Latest revision as of 08:23, 10 April 2023
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 |