Show simple item record

dc.contributor.authorEscoffier, Bruno
dc.contributor.authorMonnot, Jérôme
dc.date.accessioned2009-09-10T14:12:18Z
dc.date.available2009-09-10T14:12:18Z
dc.date.issued2008
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/1542
dc.descriptionVersion préliminaire dans Cahiers du LAMSADE N° 261en
dc.language.isoenen
dc.subjectTraveling salesman problemen
dc.subjectDifferential ratioen
dc.subjectApproximation algorithmen
dc.subject.ddc005en
dc.titleA Better differential approximation ratio for symmetric TSPen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn this paper, we study the approximability properties of symmetric TSP under an approximation measure called the differential ratio. More precisely, we improve up to 3/4−ε (for any ε>0) the best differential ratio of 2/3 known so far, given in Hassin and Khuller, [R. Hassin, S. Khuller, z-approximations, J. Algorithms, 41 (2) (2001) 429–442].en
dc.relation.isversionofjnlnameTheoretical Computer Science
dc.relation.isversionofjnlvol396en
dc.relation.isversionofjnlissue1-3en
dc.relation.isversionofjnldate2008-05
dc.relation.isversionofjnlpages63-70en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.tcs.2008.01.002en
dc.description.sponsorshipprivatenonen
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record