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 xth 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