Thumbnail

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

Toulouse, Sophie; Paschos, Vangelis; Monnot, Jérôme (2003), Differential approximation results for the traveling salesman problem with distances 1 and 2, European Journal of Operational Research, 145, 3, p. 557-568. http://dx.doi.org/10.1016/S0377-2217(02)00222-9

View/Open
Type
Article accepté pour publication ou publié
Date
2003
Journal name
European Journal of Operational Research
Volume
145
Number
3
Pages
557-568
Publication identifier
Metadata
Show full item record
Author(s)
Toulouse, Sophie cc
Paschos, Vangelis
Monnot, Jérôme cc
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.
Subjects / Keywords
Approximation algorithm; Traveling salesman