Unweighted Set-Covering (The Set-Covering Problem)

From Algorithm Wiki
Jump to navigation Jump to search

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