New answers tagged


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 ...


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