Date
2008
Description
Version préliminaire dans Cahiers du LAMSADE N° 261
Indexation documentaire
Programmation, logiciels, organisation des données
Subject
Traveling salesman problem; Differential ratio; Approximation algorithm
Nom de la revue
Theoretical Computer Science
Volume
396
Numéro
1-3
Date de publication
05-2008
Pages article
63-70
Nom de l'éditeur
Elsevier
Auteur
Escoffier, Bruno
Monnot, Jérôme
Type
Article accepté pour publication ou publié
Résumé en anglais
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].
