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: | Vanderpooten Daniel, Bazgan Cristina, Aissi Hassene |
Keywords: | networks: path |
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.