Integer linear program Vazirani (Unweighted Set-Covering; Weighted Set-Covering The Set-Covering Problem)
Jump to navigation
Jump to search
Time Complexity
$O(n^{2})$
Space Complexity
$O(U)$ words
()
Description
ILP
Approximate?
Approximate
Approximation Factor: \log n
Randomized?
No, deterministic
Model of Computation
Word RAM
Year
2001
Reference
https://link.springer.com/chapter/10.1007/978-3-662-04565-7_13