Thumbnail

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

Monnot, Jérôme; Paschos, Vangelis; Toulouse, Sophie (2001), Differential approximation results for the traveling salesman problem with distances 1 and 2, in Freivalds, Rusins, Fundamentals of Computation Theory 13th International Symposium, FCT 2001, Riga, Latvia, August 22-24, 2001. Proceedings, Springer : Berlin, p. 275-286. http://dx.doi.org/10.1007/3-540-44669-9_27

View/Open
Type
Communication / Conférence
Date
2001
Conference title
13th International Symposium on Fundamentals of Computation Theory (FCT'01)
Conference date
2001-08
Conference city
Riga
Conference country
Lettonie
Book title
Fundamentals of Computation Theory 13th International Symposium, FCT 2001, Riga, Latvia, August 22-24, 2001. Proceedings
Book author
Freivalds, Rusins
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
2138
Published in
Berlin
ISBN
978-3-540-42487-1
Number of pages
541
Pages
275-286
Publication identifier
Metadata
Show full item record
Author(s)
Monnot, Jérôme cc
Paschos, Vangelis
Toulouse, Sophie cc
Abstract (EN)
We prove that both minimum and maximum traveling salesman problems on complete graphs with edge-distances 1 and 2 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 within better than 5379/5380 + ε.
Subjects / Keywords
Approximation ratio; Traveling Salesman; Graphs