Weighted Set-Covering (The Set-Covering Problem)

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