Weighted 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 | |||
$S$: the collection of sets | |||
$n$: number of elements in the universe | |||
H(x): the | $m$: number of sets in the collection | ||
$H(x)$: the $x^{th}$ Harmonic number | |||
== Table of Algorithms == | == Table of Algorithms == | ||
| Line 30: | 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.ezproxy.canberra.edu.au/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.ezproxy.canberra.edu.au/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.ezproxy.canberra.edu.au/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.ezproxy.canberra.edu.au/doi/10.1145/237814.237991 Time] | ||
|- | |- | ||
| [[Lund & Yannakakis ( The Set-Covering Problem)|Lund & Yannakakis]] || 1994 || $O({2}^n)$ || || Exact || Deterministic || [https://doi-org.ezproxy.canberra.edu.au/10.1145%2F185675.306789 Time] | | [[Lund & Yannakakis ( The Set-Covering Problem)|Lund & Yannakakis]] || 1994 || $O({2}^n)$ || || Exact || Deterministic || [https://doi-org.ezproxy.canberra.edu.au/10.1145%2F185675.306789 Time] | ||
| Line 36: | 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.ezproxy.canberra.edu.au/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.ezproxy.canberra.edu.au/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:24, 10 April 2023
Description
The set-covering problem where each set $s\in S$ is assigned a weight and the goal is to find the minimum weight sub-collection of $S$ that covers the universe.
Related Problems
Subproblem: Unweighted 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 |
|---|---|---|---|---|---|---|
| Chvatal greedy heuristic | 1979 | $O(dn^{2})$ | $O(dm)$ | ln n - lnln n + \Theta(1) | 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 |