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

Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel

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

Publisher

Elsevier

Pages

427-438

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