# 35-3 Weighted set-covering problem

Suppose that we generalize the set-covering problem so that each set $S_i$ in the family $\mathcal F$ has an associated weight $w_i$ and the weight of a cover $\mathcal C$ is $\sum_{S_i \in \mathcal C} w_i$. We wish to determine a minimum-weight cover. (Section 35.3 handles the case in which $w_i = 1$ for all $i$.)

Show how to generalize the greedy set-covering heuristic in a natural manner to provide an approximate solution for any instance of the weighted set-covering problem. Show that your heuristic has an approximation ratio of $H(d)$, where $d$ is the maximum size of any set $S_i$.

(Omit!)