A Better differential approximation ratio for symmetric TSP

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