Approximation of min–max and min–max regret versions of some combinatorial optimization problems

Approximation of min–max and min–max regret versions of some combinatorial optimization problems

0.00 Avg rating0 Votes
Article ID: iaor2009547
Country: Netherlands
Volume: 179
Issue: 2
Start Page Number: 281
End Page Number: 290
Publication Date: Jun 2007
Journal: European Journal of Operational Research
Authors: , ,
Keywords: networks: path
Abstract:

This paper investigates, for the first time in the literature, the approximation of min–max (regret) versions of classical problems like shortest path, minimum spanning tree, and knapsack. For a constant number of scenarios, we establish fully polynomial-time approximation schemes for the min–max versions of these problems, using relationships between multi-objective and min–max optimization. Using dynamic programming and classical trimming techniques, we construct a fully polynomial-time approximation scheme for min–max regret shortest path. We also establish a fully polynomial-time approximation scheme for min–max regret spanning tree and prove that min–max regret knapsack is not at all approximable.

Reviews

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