Efficient network algorithms for two special cases of the weighted set cover problem

Abstract

In the weighted set-cover problem, we are given a finite set S and a collection ℧ of its subsets. A non-negative weight w_j 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.

Keywords:

• Set cover problem
• efficient algorithms
• shortest path
• minimum cut

JEL Classification:

• C6
• C61
• C63
• C02
• C44

AMS Classification:

• 05B40
• 90C27
• 90C35
• 05C85

Acknowledgements

We wish to thank the editor and the anonymous referees, whose valuable comments allowed us to improve the paper.