Approximation of min–max and min–max regret versions of some combinatorial optimization problems |
| |
Authors: | Hassene Aissi Cristina Bazgan Daniel Vanderpooten |
| |
Institution: | LAMSADE, Université Paris-Dauphine, Place du Marechal de Lattre de Ta., 75775 Paris Cedex 16, France |
| |
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. For a non-constant 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. |
| |
Keywords: | Min&ndash max Min&ndash max regret Approximation fptas Shortest path Minimum spanning tree Knapsack |
本文献已被 ScienceDirect 等数据库收录! |
|