Show simple item record

hal.structure.identifier
dc.contributor.authorAissi, Hassene*
hal.structure.identifier
dc.contributor.authorBazgan, Cristina*
hal.structure.identifier
dc.contributor.authorVanderpooten, Daniel*
dc.date.accessioned2011-04-04T09:59:22Z
dc.date.available2011-04-04T09:59:22Z
dc.date.issued2006
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5871
dc.language.isoenen
dc.subjectshortest path
dc.subjectapproximation
dc.subjectmin-max regret
dc.subjectfptas
dc.subjectmin-max
dc.subjectminimum spanning tree
dc.subject.ddc003en
dc.titleApproximating min-max (regret) versions of some polynomial problems
dc.typeCommunication / Conférence
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 a general approximation scheme which can be used for min-max and min-max regret versions of some polynomial problems. Applying this scheme to shortest path and minimum spanning tree, we obtain fully polynomial-time approximation schemes with much better running times than the ones previously presented in the literature.
dc.identifier.citationpages428-438
dc.relation.ispartoftitleComputing and Combinatorics 12th Annual International Conference, COCOON 2006, Taipei, Taiwan, August 15-18, 2006, Proceedings
dc.relation.ispartofeditorLee, D.T.
dc.relation.ispartofpublnameSpringer
dc.relation.ispartofpublcityBerlin Heidelberg
dc.relation.ispartofdate2006
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-540-36925-7
dc.relation.confcountryTAIWAN, PROVINCE OF CHINA
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.date.updated2017-01-05T15:31:09Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record