ISSN:
1572-9338
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Notes:
Abstract 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. We 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02025298
Permalink