Article ID: | iaor19941224 |
Country: | Switzerland |
Volume: | 43 |
Issue: | 1/4 |
Start Page Number: | 279 |
End Page Number: | 284 |
Publication Date: | Oct 1993 |
Journal: | Annals of Operations Research |
Authors: | Vohra Rakesh V., Hall Nicholas G. |
Keywords: | heuristics |
The set covering problem has many diverse applications to problems arising in crew scheduling, facility location and other business areas. Since the problem is known to be hard to solve optimally, a number of approximate (heuristic) approaches have been designed for it. These approaches (with one exception) divide into two main groups, greedy heuristics and dual saturation heuristics. The authors use the concept of a Pareto optimal dual solution to show that an arbitrary dual saturation heuristic has the same worst-case performance guarantee as the two best known heuristics of that type. Moreover, this poor performance level is always attainable by those two heuristics.