New answers tagged traveling-salesman
1
In your first sentence you mixed up "decision problem" and "optimality problem". They are different problems. One is: Given a list of cities and a distance d, can you visit all cities with a tour of length ≤ d? This is easily verified in linear time if I give you a sorted list of the cities. The other is: Given a list of cities, what is ...
0
The statement is for Euclidean TSP only, and as you mention yourself, it is only used as a heuristic.
But try to create an example yourself and see what happens when you have crossing links as part of your solution:
From Urban OR:
Property 1: The optimum traveling salesman tour does not intersect itself.
Top 50 recent answers are included
