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
TypeArticle accepté pour publication ou publié
Journal nameEuropean Journal of Operational Research
MetadataShow full item record
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 / KeywordsApproximation algorithm; Traveling salesman
Showing items related by title and author.