Unweighted Set-Covering: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 29: | Line 29: | ||
| [[Alon; Moshkovitz & Safra (Unweighted Set-Covering The Set-Covering Problem)|Alon; Moshkovitz & Safra]] || 2006 || $O(nlogn)$ || || || Deterministic || [https://dl.acm.org/doi/pdf/10.1145/1150334.1150336 Time] | | [[Alon; Moshkovitz & Safra (Unweighted Set-Covering The Set-Covering Problem)|Alon; Moshkovitz & Safra]] || 2006 || $O(nlogn)$ || || || Deterministic || [https://dl.acm.org/doi/pdf/10.1145/1150334.1150336 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] | ||
Revision as of 13:05, 15 February 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 xth 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 |