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
2009Journal name
European Journal of Operational ResearchVolume
197Number
2Publisher
Elsevier
Pages
427-438
Publication identifier
Metadata
Show full item recordAbstract (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–maxRelated items
Showing items related by title and author.
-
Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2007) Article accepté pour publication ou publié
-
Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2005) Article accepté pour publication ou publié
-
Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2005) Communication / Conférence
-
Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2008) Article accepté pour publication ou publié
-
Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2010) Article accepté pour publication ou publié