Name
Abstract | ||
|---|---|---|
This paper is concerned with finding two solutions of a set covering problem that have a minimum number of variables in common. We show that this problem is NP-complete, even in the case where we are only interested in completely disjoint solutions. We describe three heuristic methods based on the standard 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 covering problem. Finally, extensive computational tests are given demonstrating the nature of these algorithms. These tests are carried out both on randomly generated problems and on problems found in the literature. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1023/A:1009687403254 | J. Heuristics |
Keywords | Field | DocType |
set covering,disjoint solutions,GRASP algorithm | Discrete mathematics,Set cover problem,Heuristic,Mathematical optimization,NP-complete,Disjoint sets,Greedy algorithm,Set packing,Local search (optimization),Mathematics,Covering problems | Journal |
Volume | Issue | ISSN |
7 | 2 | 1572-9397 |
Citations | PageRank | References |
2 | 0.36 | 2 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter L. Hammer | 1 | 1996 | 288.93 |
| David J. Rader, Jr. | 2 | 8 | 1.14 |