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

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Differential approximation results for the traveling salesman problem with distances 1 and 2

Thumbnail
View/Open
publi144.pdf (394.0Kb)
Date
2003
Dewey
Recherche opérationnelle
Sujet
Approximation algorithm; Traveling salesman
Journal issue
European Journal of Operational Research
Volume
145
Number
3
Publication date
03-2003
Article pages
557-568
DOI
http://dx.doi.org/10.1016/S0377-2217(02)00222-9
URI
https://basepub.dauphine.fr/handle/123456789/1663
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Toulouse, Sophie
Paschos, Vangelis
Monnot, Jérôme
Type
Article accepté pour publication ou publié
Abstract (EN)
We prove that both minimum and maximum traveling salesman problems on complete graphs with edge-distances 1 and 2 (denoted by min_TSP12 and max_TSP12, respectively) are approximable within 3/4. Based upon this result, we improve the standard-approximation ratio known for maximum traveling salesman with distances 1 and 2 from 3/4 to 7/8. Finally, we prove that, for any ε>0, it is NP-hard to approximate both problems better than within 741/742+ε. The same results hold when dealing with a generalization of min_ and max_TSP12, where instead of 1 and 2, edges are valued by a and b.

  • 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

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.