Show simple item record

dc.contributor.authorBazgan, Cristina*
dc.contributor.authorGourvès, Laurent*
dc.contributor.authorMonnot, Jérôme*
dc.contributor.authorPascual, Fanny*
dc.date.accessioned2012-04-24T12:07:38Z
dc.date.available2012-04-24T12:07:38Z
dc.date.issued2012
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/9034
dc.language.isoenen
dc.subjectHamiltonian cycle
dc.subjectSingle Approximation
dc.subject.ddc003en
dc.titleSingle Approximation for Biobjective Max TSP
dc.typeCommunication / Conférence
dc.contributor.editoruniversityotherLIP6, Université Pierre et Marie Curie;France
dc.contributor.editoruniversityotherInstitut Universitaire de France;France
dc.contributor.editoruniversityotherCNRS, UMR 7243;France
dc.description.abstractenWe propose an algorithm which returns a single Hamiltonian cycle with performance guarantee on both objectives. The algorithm is analysed in three cases. When both (resp. at least one) objective function(s) fulfill(s) the triangle inequality, the approximation ratio is 512−041 (resp. 83−). When the triangle inequality is not assumed on any objective function, the algorithm is 141+22−027 -approximate.
dc.identifier.citationpages49-62
dc.relation.ispartoftitleApproximation and Online Algorithms 9th International Workshop, WAOA 2011, Saarbrücken, Germany, September 8-9, 2011, Revised Selected Papers
dc.relation.ispartofeditorSolis-Oba, Roberto
dc.relation.ispartofpublnameSpringer
dc.relation.ispartofpublcityBerlin Heidelberg
dc.relation.ispartofdate2012
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/978-3-642-29116-6
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-642-29115-9
dc.relation.conftitle9th International Workshop on Approximation and Online Algorithms, WAOA 2011
dc.relation.confdate2011-09
dc.relation.confcitySaarbrücken
dc.relation.confcountryGermany
dc.identifier.doi10.1007/978-3-642-29116-6_5
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2017-01-05T14:58:20Z
hal.person.labIds989*
hal.person.labIds989*
hal.person.labIds989*
hal.person.labIds233*
hal.faultCode{"duplicate-entry":{"hal-01282507":{"doi":"1.0"}}}


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