Show simple item record

dc.contributor.authorToulouse, Sophie
dc.contributor.authorPaschos, Vangelis
dc.contributor.authorMonnot, Jérôme
dc.date.accessioned2009-09-15T16:26:18Z
dc.date.available2009-09-15T16:26:18Z
dc.date.issued2003
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/1663
dc.language.isoenen
dc.subjectApproximation algorithmen
dc.subjectTraveling salesmanen
dc.subject.ddc003en
dc.titleDifferential approximation results for the traveling salesman problem with distances 1 and 2en
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe prove that both minimum and maximum traveling salesman problems on complete graphs with edge-distances 1 and 2 (denoted by min_TSP12 and max_TSP12, respectively) 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 better than within 741/742+ε. The same results hold when dealing with a generalization of min_ and max_TSP12, where instead of 1 and 2, edges are valued by a and b.en
dc.relation.isversionofjnlnameEuropean Journal of Operational Research
dc.relation.isversionofjnlvol145en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate2003-03
dc.relation.isversionofjnlpages557-568en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/S0377-2217(02)00222-9en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record