• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
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
http://dx.doi.org/10.1016/j.ejor.2008.09.012
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

Related items

Showing items related by title and author.

  • Thumbnail
    Approximation of min-max and min-max regret versions of some combinatorial optimization problems 
    Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2007) Article accepté pour publication ou publié
  • Thumbnail
    Complexity of the min-max and min-max regret assignment problems 
    Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2005) Article accepté pour publication ou publié
  • Thumbnail
    Complexity of the min-max (regret) versions of cut problems 
    Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2005) Communication / Conférence
  • Thumbnail
    Complexity of the min-max (regret) versions of cut problems 
    Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2008) Article accepté pour publication ou publié
  • Thumbnail
    General approximation schemes for min–max (regret) versions of some (pseudo-)polynomial problems 
    Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2010) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo