Weighted Set-Covering

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