Show simple item record

dc.contributor.authorAissi, Hassene*
dc.contributor.authorBazgan, Cristina*
dc.contributor.authorVanderpooten, Daniel*
dc.date.accessioned2009-10-13T09:27:00Z
dc.date.available2009-10-13T09:27:00Z
dc.date.issued2007
dc.identifier.issn0377-2217
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2220
dc.language.isoenen
dc.subjectKnapsack
dc.subjectMin–max regret
dc.subjectShortest path
dc.subjectMinimum spanning tree
dc.subjectApproximation
dc.subject.ddc511en
dc.titleApproximation of min-max and min-max regret versions of some combinatorial optimization problems
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThis paper investigates, for the first time in the literature, the approximation of min–max (regret) versions of classical problems like shortest path, minimum spanning tree, and knapsack. For a constant number of scenarios, we establish fully polynomial-time approximation schemes for the min–max versions of these problems, using relationships between multi-objective and min–max optimization. Using dynamic programming and classical trimming techniques, we construct a fully polynomial-time approximation scheme for min–max regret shortest path. We also establish a fully polynomial-time approximation scheme for min–max regret spanning tree and prove that min–max regret knapsack is not at all approximable. For a non-constant number of scenarios, in which case min–max and min–max regret versions of polynomial-time solvable problems usually become strongly NP-hard, non-approximability results are provided for min–max (regret) versions of shortest path and spanning tree.
dc.relation.isversionofjnlnameEuropean Journal of Operational Research
dc.relation.isversionofjnlvol179
dc.relation.isversionofjnlissue2
dc.relation.isversionofjnldate2007
dc.relation.isversionofjnlpages281-290
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.ejor.2006.03.023
dc.description.sponsorshipprivateouien
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2016-10-06T09:48:30Z
hal.person.labIds*
hal.person.labIds*
hal.person.labIds*


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