Weighted Set-Covering (The Set-Covering Problem)

From Algorithm Wiki
Jump to navigation Jump to search


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


$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