Afficher la notice abrégée

dc.contributor.authorAissi, Hassene*
dc.contributor.authorBazgan, Cristina*
dc.contributor.authorVanderpooten, Daniel*
dc.date.accessioned2011-09-16T11:31:22Z
dc.date.available2011-09-16T11:31:22Z
dc.date.issued2010
dc.identifier.issn1572-5286
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/6966
dc.language.isoenen
dc.subjectKnapsack
dc.subjectMinimum spanning tree
dc.subjectMin–max regret
dc.subjectFptas
dc.subjectMin–max
dc.subjectShortest path
dc.subjectMinimum weighted perfect matching
dc.subjectApproximation
dc.subject.ddc003en
dc.titleGeneral approximation schemes for min–max (regret) versions of some (pseudo-)polynomial problems
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWhile the complexity of min–max and min–max regret versions of most classical combinatorial optimization problems has been thoroughly investigated, there are very few studies about their approximation. For a bounded number of scenarios, we establish general approximation schemes which can be used for min–max and min–max regret versions of some polynomial or pseudo-polynomial problems. Applying these schemes to shortest path, minimum spanning tree, minimum weighted perfect matching on planar graphs, and knapsack problems, we obtain fully polynomial-time approximation schemes with better running times than the ones previously presented in the literature.
dc.relation.isversionofjnlnameDiscrete Optimization
dc.relation.isversionofjnlvol7
dc.relation.isversionofjnlissue3
dc.relation.isversionofjnldate2010
dc.relation.isversionofjnlpages136-148
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.disopt.2010.03.004
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevier
dc.subject.ddclabelRecherche opérationnelleen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2016-10-06T09:41:36Z
hal.person.labIds*
hal.person.labIds*
hal.person.labIds*


Fichiers attachés à cette notice

FichiersTailleFormatConsulter

Il n'y a pas de fichiers associés à cette notice.

Ce document fait partie de la (des) collection(s) suivante(s)

Afficher la notice abrégée