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

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

0.00 Avg rating0 Votes
Article ID: iaor20042871
Country: Netherlands
Volume: 145
Issue: 3
Start Page Number: 557
End Page Number: 568
Publication Date: Mar 2003
Journal: European Journal of Operational Research
Authors: , ,
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.