dc.contributor.author | Escoffier, Bruno | |
dc.contributor.author | Monnot, Jérôme | |
dc.date.accessioned | 2009-09-10T14:12:18Z | |
dc.date.available | 2009-09-10T14:12:18Z | |
dc.date.issued | 2008 | |
dc.identifier.uri | https://basepub.dauphine.fr/handle/123456789/1542 | |
dc.description | Version préliminaire dans Cahiers du LAMSADE N° 261 | en |
dc.language.iso | en | en |
dc.subject | Traveling salesman problem | en |
dc.subject | Differential ratio | en |
dc.subject | Approximation algorithm | en |
dc.subject.ddc | 005 | en |
dc.title | A Better differential approximation ratio for symmetric TSP | en |
dc.type | Article accepté pour publication ou publié | |
dc.description.abstracten | In 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.isversionofjnlname | Theoretical Computer Science | |
dc.relation.isversionofjnlvol | 396 | en |
dc.relation.isversionofjnlissue | 1-3 | en |
dc.relation.isversionofjnldate | 2008-05 | |
dc.relation.isversionofjnlpages | 63-70 | en |
dc.relation.isversionofdoi | http://dx.doi.org/10.1016/j.tcs.2008.01.002 | en |
dc.description.sponsorshipprivate | non | en |
dc.relation.isversionofjnlpublisher | Elsevier | en |
dc.subject.ddclabel | Programmation, logiciels, organisation des données | en |