Weighted Set-Covering

The set-covering problem where each set $s\in S$ is assigned a weight and the goal is to find the minimum weight sub-collection of $S$ that covers 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 2 of 2 algorithms

				See more
Vazirani (ILP, chapters 13-15)	2001	$O(\text{poly}(n, d))$	$O(U)$
Chvatal greedy heuristic	1979	$O(dn^2)$	$O(dm)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms