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:06
This question appears to be offtopic. The users who voted to close gave this specific reason:
 "MathOverflow is for mathematicians to ask each other questions about their research. See Math.StackExchange to ask general questions in mathematics." – Ricardo Andrade, Chris Godsil, Ryan Budney, Stefan Kohl
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) 

