Approximation of min-max and min-max regret versions of some combinatorial optimization problems
Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2007), Approximation of min-max and min-max regret versions of some combinatorial optimization problems, European Journal of Operational Research, 179, 2, p. 281-290. http://dx.doi.org/10.1016/j.ejor.2006.03.023
Type
Article accepté pour publication ou publiéDate
2007Journal name
European Journal of Operational ResearchVolume
179Number
2Pages
281-290
Publication identifier
Metadata
Show full item recordAbstract (EN)
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.Subjects / Keywords
Knapsack; Min–max regret; Shortest path; Minimum spanning tree; ApproximationRelated items
Showing items related by title and author.
-
Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2009) Article accepté pour publication ou publié
-
Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2010) Article accepté pour publication ou publié
-
Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2006) Communication / Conférence
-
Approximation complexity of min-max (regret) versions of shortest path, spanning tree, and knapsack Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2005) Communication / Conférence
-
Aissi, Hassene (2006) Article accepté pour publication ou publié