set cover problem

formulation

Given a universe $\mathcal{U}$ and a family $\mathcal{S}$ of subsets of $\mathcal{U}$ , a cover is a subfamily $\mathcal{C}\subseteq \mathcal{S}$ of sets whose union is $\mathcal{U}$. In the set covering decision problem, the input is a pair $(\mathcal{U},\mathcal{S})$ and an integer $k$ ; the question is whether there is a set covering of size $k$ or less. In the set covering optimization problem, the input is a pair $(\mathcal{U},\mathcal{S})$, and the task is to find a set covering that uses the fewest sets.

the decision problem is NP-complete, optimization is NP-hard.

greedy algorithm

There is a greedy algorithm for polynomial time approximation of set covering that chooses sets according to one rule: at each stage, choose the set that contains the largest number of uncovered elements.

It can be shown that this algorithm achieves an approximation ratio of $H(s)$, where $s$ is the size of the set to be covered. In other words, it finds a covering that may be $H(n)$ times as large as the minimum one, where $H(n)$ is the nth harmonic number