Unweighted Set-Covering

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.

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

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 1 of 1 algorithms

				See more
Vazirani (ILP, chapters 13-15)	2001	$O(\text{poly}(n, d))$	$O(U)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms

Displaying 1 of 1 other relevant algorithms