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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.