Abstract
In the weighted set-cover problem, we are given a finite set S and a collection ℧ of its subsets. A non-negative weight wj is associated with each . The problem is to find a subcollection of ℧ with minimum weight so that the union of its sets is equal to . This problem is a classic NP-hard combinatorial problem. In this paper, we investigate two special cases of the problem that can be solved in strongly polynomial time. The first is the case where any two sets either have empty intersection or overlap completely. It is shown how this case may be transformed to a minimum cut problem. The second case is where we can sort the elements of S into an order in which the elements of each set of ℧ appear consecutively. It is proved that this case reduces to a shortest path problem. In either case, examples are given to illustrate the methods.
Acknowledgements
We wish to thank the editor and the anonymous referees, whose valuable comments allowed us to improve the paper.