View source for Unweighted Set-Covering

{{DISPLAYTITLE: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 == 

{| class="wikitable sortable"  style="text-align:center;" width="100%"

! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference

|-

| [[Alon; Moshkovitz & Safra (Unweighted Set-Covering The Set-Covering Problem)|Alon; Moshkovitz & Safra]] || 2006 || $O(nlogn)$ ||  ||  || Deterministic || [https://dl-acm-org.ezproxy.canberra.edu.au/doi/pdf/10.1145/1150334.1150336 Time]
|-
| [[Integer linear program Vazirani (Unweighted Set-Covering; Weighted Set-Covering The Set-Covering Problem)|Integer linear program Vazirani]] || 2001 || $O(n^{2})$ || $O(U)$ || \log n || Deterministic || [https://link-springer-com.ezproxy.canberra.edu.au/chapter/10.1007/978-3-662-04565-7_13 Time]
|-
| [[Greedy Algorithm ( The Set-Covering Problem)|Greedy Algorithm]] || 1996 || $O(n^{3} log n)$ || $O(U)$ || \ln(n) - \ln(\ln(n)) + \Theta(1) || Deterministic || [https://dl-acm-org.ezproxy.canberra.edu.au/doi/10.1145/237814.237991 Time]
|-
| [[Lund & Yannakakis ( The Set-Covering Problem)|Lund & Yannakakis]] || 1994 || $O({2}^n)$ ||  || Exact || Deterministic || [https://doi-org.ezproxy.canberra.edu.au/10.1145%2F185675.306789 Time]
|-
| [[Feige ( The Set-Covering Problem)|Feige]] || 1998 || $O({2}^n)$ ||  || Exact || Deterministic || [https://courses.cs.duke.edu/spring07/cps296.2/papers/p634-feige.pdf Time]
|-
| [[Raz & Safra ( The Set-Covering Problem)|Raz & Safra]] || 1997 || $O(n^{3} log^{3} n)$ ||  || Exact || Deterministic || [https://dl-acm-org.ezproxy.canberra.edu.au/doi/10.1145/258533.258641 Time]
|-
| [[Dinur & Steurer ( The Set-Covering Problem)|Dinur & Steurer]] || 2013 || $O(n^{2} log n)$ ||  || Exact || Deterministic || [https://www.dsteurer.org/paper/productgames.pdf Time]
|-
| [[Cardoso; Nuno; Abreu; Rui ( The Set-Covering Problem)|Cardoso; Nuno; Abreu; Rui]] || 2014 || $O(n^{2})$ ||  || Exact || Parallel || [https://www.semanticscholar.org/paper/An-efficient-distributed-algorithm-for-computing-Cardoso-Abreu/ce32696c1176800c5b90fab026bf93f282e2b161 Time]
|-
| [[Brute force ( The Set-Covering Problem)|Brute force]] || 1972 || $O(U {2}^n)$ || $O(U)$ || Exact || Deterministic ||  
|-
|}