Does there exist an instance of the travelling salesman problem where the optimal solution has edges that cross?
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.
closed as offtopic by Ricardo Andrade, Lucia, Chris Godsil, Ryan Budney, Stefan Kohl Apr 14 at 23:06This question appears to be offtopic. The users who voted to close gave this specific reason:



I've answered this in http://stackoverflow.com/questions/2444125/crossingedgesinthetravellingsalesmanproblem/2444288#2444288. 


Yes, as long as your distance does not satisfy the triangle inequality. Here is a series of points which form a shortest route under the Hamming distance. If you plot them on the plane, you will notice that they cross over. (1,1) (1,2) (4,2) (3,2) (0,2) (0,1) 

