Maximally disjoint solutions of the set covering problem

This paper is concerned with finding two solutions of a set covering proble m that have a minimum number of variables in common. We show that this prob lem is NP-complete, even in the case where we are only interested in comple tely disjoint solutions. We describe three heuristic methods based on the s tandard greedy algorithm for set covering problems. Two of these algorithms find the solutions sequentially, while the third finds them simultaneously . A local search method for reducing the overlap of the two given solutions is then described. This method involves the solution of a reduced set cove ring problem. Finally, extensive computational tests are given demonstratin g the nature of these algorithms. These tests are carried out both on rando mly generated problems and on problems found in the literature.