Unweighted Set-Covering (The Set-Covering Problem)

Description

Given a universe $U$, i.e. a set of elements $\{1, 2, \ldots, n\}$, and a collection $S$ of $m$ sets whose union is the universe, identify the smallest sub-collection of $S$ whose union is the universe.

Related Problems

Generalizations: Weighted 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
Alon; Moshkovitz & Safra	2006	$O(nlogn)$			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