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!)

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用