Pareto optimality and a class of set covering heuristics

Pareto optimality and a class of set covering heuristics

0.00 Avg rating0 Votes
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: ,
Keywords: heuristics
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. 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.

Reviews

Required fields are marked *. Your email address will not be published.