# Unweighted Set-Covering (The Set-Covering Problem)

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 |