Thumbnail - No thumbnail

Min–max and min–max regret versions of combinatorial optimization problems: A survey

Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2009), Min–max and min–max regret versions of combinatorial optimization problems: A survey, European Journal of Operational Research, 197, 2, p. 427-438. http://dx.doi.org/10.1016/j.ejor.2008.09.012

Type
Article accepté pour publication ou publié
External document link
http://hal.archives-ouvertes.fr/hal-00158652/en/
Date
2009
Journal name
European Journal of Operational Research
Volume
197
Number
2
Publisher
Elsevier
Pages
427-438
Publication identifier
Metadata
Show full item record
Author(s)
Aissi, Hassene
Bazgan, Cristina
Vanderpooten, Daniel
Abstract (FR)
Les critères min-max et min-max regret sont souvent utilisés en vue d'obtenir des solutions robustes. Après avoir motivé l'utilisation de ces critères, nous présentons des résultats généraux. Ensuite, nous donnons des résultats de complexité des versions min-max et min-max regret de quelques problèmes d'optimisation combinatoire : plus court chemin, arbre couvrant, affectation, coupe, s − t coupe, sac à dos. Comme la plupart de ces problèmes sont NP-difficiles, nous présentons des algorithmes d'approximation ainsi que des algorithmes exacts de résolution.
Abstract (EN)
Min–max and min–max regret criteria are commonly used to define robust solutions. After motivating the use of these criteria, we present general results. Then, we survey complexity results for the min–max and min–max regret versions of some combinatorial optimization problems: shortest path, spanning tree, assignment, min cut, min s–t cut, knapsack. Since most of these problems are NP-hard, we also investigate the approximability of these problems. Furthermore, we present algorithms to solve these problems to optimality.
Subjects / Keywords
Robustness; Approximation; Complexity; Combinatorial optimization; Min–max regret; Min–max