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

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. For a non-constat number of scenarios, in which case min max and min-max regret versions of polynomial-time solvable problems usually become strongly NP-hard, non-approximability results are provided for min-max (regret) versions of shortest path and spanning tree. (c) 2006 Elsevier B.V. All rights reserved.