# Weighted-Set Cover Approximation

So in the weighted-set cover problem, I need to determine the minimum weight cover. My algorithm calculates the efficiency for each set:

Efficiency = # of uncovered items in set / weight of set


And I will pick the set with the highest value. This strategy works because you want to have want to pick a set with the largest number of uncovered items and smallest set the higher the efficiency, the closer we achieve that. Now I need to prove that my algorithm has an approximation ratio of H(d) where d is the maximum size of any set.

• What did you try, where are you stuck? Is there a question in there as well? – Pål GD Apr 22 at 20:29