Show simple item record

dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.contributor.authorPaschos, Vangelis
dc.contributor.authorToulouse, Sophie
HAL ID: 177689
ORCID: 0000-0002-6689-1008
dc.date.accessioned2011-04-04T12:10:09Z
dc.date.available2011-04-04T12:10:09Z
dc.date.issued2001
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5875
dc.language.isoenen
dc.subjectApproximation ratioen
dc.subjectTraveling Salesmanen
dc.subjectGraphsen
dc.subject.ddc003en
dc.titleDifferential approximation results for the traveling salesman problem with distances 1 and 2en
dc.typeCommunication / Conférence
dc.description.abstractenWe prove that both minimum and maximum traveling salesman problems on complete graphs with edge-distances 1 and 2 are approximable within 3/4. Based upon this result, we improve the standard approximation ratio known for maximum traveling salesman with distances 1 and 2 from 3/4 to 7/8. Finally, we prove that, for any ε > 0, it is NP-hard to approximate both problems within better than 5379/5380 + ε.en
dc.identifier.citationpages275-286en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber2138
dc.relation.ispartoftitleFundamentals of Computation Theory 13th International Symposium, FCT 2001, Riga, Latvia, August 22-24, 2001. Proceedingsen
dc.relation.ispartofeditorFreivalds, Rusins
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2001
dc.relation.ispartofpages541en
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/3-540-44669-9en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-540-42487-1en
dc.relation.conftitle13th International Symposium on Fundamentals of Computation Theory (FCT'01)en
dc.relation.confdate2001-08
dc.relation.confcityRigaen
dc.relation.confcountryLettonieen
dc.identifier.doihttp://dx.doi.org/10.1007/3-540-44669-9_27


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record