A New Efficient Heuristic for the Minimum Set Covering Problem

We solve approximately the minimum set covering problem by developing a new heuristic, which is essentially based on the flow algorithm originally developed by Ford and Fulkerson. We perform a comparative study of the performances (concerning solution qualities and execution times) of the flow algorithm as well as of the natural greedy heuristic for set covering originally studied by Johnson and Lovász.