A special class of set covering problems

A class of set covering problems is being introduced. This class is obtained from reformulation of a well-known combinatorial problem of Erdös on the hypercube. An algorithmic method of solution to the problem is proposed. Max-flow algorithms are the main ingredients of our method. The computational results which will be presented here improve the best existing bound related to the combinatorial problem. This, at the same time, provides a good approximate solution to the corresponding set covering problem of more than a thousand variables and constraints. Moreover, we show that our special class of problems can be recognized from the class of all set covering problems, by a polynomial algorithm with O(MN) complexity, where M and N are numbers of constraints and variables of a given instant, respectively.