Weighted Set-Covering (The Set-Covering Problem)
Jump to navigation
Jump to search
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 |
| 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 |