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.