Weighted Set-Covering: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 27: | Line 27: | ||
| [[Chvatal greedy heuristic (Weighted Set-Covering The Set-Covering Problem)|Chvatal greedy heuristic]] || 1979 || $O(dn^{2})$ || $O(dm)$ || ln n - lnln n + \Theta(1) || Deterministic || [https://www.jstor.org/stable/3689577#metadata_info_tab_contents Time] | | [[Chvatal greedy heuristic (Weighted Set-Covering The Set-Covering Problem)|Chvatal greedy heuristic]] || 1979 || $O(dn^{2})$ || $O(dm)$ || ln n - lnln n + \Theta(1) || Deterministic || [https://www.jstor.org/stable/3689577#metadata_info_tab_contents 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
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
n: number of elements in the universe
m: number of sets in the collection
d: size of the largest set in collection
H(x): the xth 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 |