Show simple item record

dc.contributor.authorAissi, Hassene
dc.contributor.authorBazgan, Cristina
dc.contributor.authorVanderpooten, Daniel
dc.date.accessioned2010-04-12T12:56:39Z
dc.date.available2010-04-12T12:56:39Z
dc.date.issued2009
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3932
dc.descriptionPublié dans les Annales du LAMSADE, n°7, 2007, p.1-32
dc.description.abstractfrLes 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.
dc.language.isoenen
dc.subjectRobustnessen
dc.subjectApproximationen
dc.subjectComplexityen
dc.subjectCombinatorial optimizationen
dc.subjectMin–max regreten
dc.subjectMin–maxen
dc.subject.ddc003en
dc.titleMin–max and min–max regret versions of combinatorial optimization problems: A surveyen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenMin–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.en
dc.relation.isversionofjnlnameEuropean Journal of Operational Research
dc.relation.isversionofjnlvol197en
dc.relation.isversionofjnlissue2en
dc.relation.isversionofjnldate2009-09
dc.relation.isversionofjnlpages427-438en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.ejor.2008.09.012en
dc.identifier.urlsitehttp://hal.archives-ouvertes.fr/hal-00158652/en/
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record