• français
    • English
  • français 
    • français
    • English
  • Connexion
JavaScript is disabled for your browser. Some features of this site may not work without it.
Accueil

Afficher

Cette collectionPar Date de CréationAuteursTitresSujetsNoms de revueToute la baseCentres de recherche & CollectionsPar Date de CréationAuteursTitresSujetsNoms de revue

Mon compte

Connexion

Statistiques

Afficher les statistiques d'usage

Approximation algorithms for the traveling salesman problem

Thumbnail
Ouvrir
publi147.pdf (394.0Kb)
Date
2003
Indexation documentaire
Recherche opérationnelle
Subject
Approximation algorithms; NP-complete problem; Traveling salesman
Nom de la revue
Mathematical Methods of Operations Research
Volume
56
Numéro
3
Date de publication
01-2003
Pages article
387-405
Nom de l'éditeur
Springer
DOI
http://dx.doi.org/10.1007/s001860200239
URI
https://basepub.dauphine.fr/handle/123456789/2980
Collections
  • LAMSADE : Publications
Métadonnées
Afficher la notice complète
Auteur
Paschos, Vangelis
Monnot, Jérôme
Toulouse, Sophie
Type
Article accepté pour publication ou publié
Résumé en anglais
We first prove that the minimum and maximum traveling salesman problems, their metric versions as well as some versions defined on parameterized triangle inequalities (called sharpened and relaxed metric traveling salesman) are all equi-approximable under an approximation measure, called differential-approximation ratio, that measures how the value of an approximate solution is placed in the interval between the worst- and the best-value solutions of an instance. We next show that the 2OPT, one of the most-known traveling salesman algorithms, approximately solves all these problems within differential-approximation ratio bounded above by 1/2. We analyze the approximation behavior of 2OPT when used to approximately solve traveling salesman problem in bipartite graphs and prove that it achieves differential-approximation ratio bounded above by 1/2 also in this case. We also prove that, for any ε>0, it is NP-hard to differentially approximate metric traveling salesman within better than 649/650 + ε and traveling salesman with distances 1 and 2 within better than 741/742 + ε. Finally, we study the standard approximation of the maximum sharpened and relaxed metric traveling salesman problems. These are versions of maximum metric traveling salesman defined on parameterized triangle inequalities and, to our knowledge, they have not been studied until now.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Cette création est mise à disposition sous un contrat Creative Commons.