I remember that I saw once an alternative to the greedy set cover algorithm that works as follows:
- Assign weight 1 to every element in the universe. Repeat steps 2 and 3 until the universe is covered:
- Pick a set for which the sum of weights of all the elements it contains is maximal.
- Double the weights of all uncovered elements.
I remember that it was also log(n) approximation, though I don't know how to show it. Is there some known technique for that kind of algorithms, in which appropriate global weight/cost on all the elements can give some approximation guarantees?