Approximation Algorithms for the Set Covering and Vertex Cover Problems
Dorit S. Hochbaum · SIAM Journal on Computing · 1982
We propose a heuristic that delivers in $O(n^3 )$ steps a solution for the set covering problem the value of which does not exceed the maximum number of sets covering an element times the optimal value.