Unweighted Set-Covering: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
(Created page with "{{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 == <pre>U: the universe of elements to be covered S: the collection of sets n: number of elements...")
 
No edit summary
 
(2 intermediate revisions by the same user not shown)
Line 10: Line 10:
== Parameters ==  
== Parameters ==  


<pre>U: the universe of elements to be covered
$U$: the universe of elements to be covered
S: the collection of sets
 
n: number of elements in the universe
$S$: the collection of sets
m: number of sets in the collection
 
H(x): the xth Harmonic number</pre>
$n$: number of elements in the universe
 
$m$: number of sets in the collection
 
$H(x)$: the $x^{th}$ Harmonic number


== Table of Algorithms ==  
== Table of Algorithms ==  
Line 26: Line 30:
| [[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]
| [[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]
|-
|-
| [[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]
| [[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]
| [[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]
Line 32: Line 38:
| [[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]
| [[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]
| [[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]
| [[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]
| [[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]

Latest revision as of 09:23, 10 April 2023

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