Travelling Salesman Problem [closed]

Does there exist an instance of the travelling salesman problem where the optimal solution has edges that cross?

-

closed as off-topic by Ricardo Andrade, Lucia, Chris Godsil, Ryan Budney, Stefan KohlApr 14 '14 at 23:06

This question appears to be off-topic. 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
If this question can be reworded to fit the rules in the help center, please edit the question.

No. Any pair of crossing edges can be replaced with a pair of noncrossing edges, which strictly decreases the total length of the path by the triangle inequality. – Qiaochu Yuan Mar 14 '10 at 22:51
It depends on if one is working with sites drawn in the plane and if the edges are weighted with Euclidean distances. If one has arbitrary weights and the weights do not obey the triangle inequality then in a drawing of a shortest weight tour, edges may cross. – Joseph Malkevitch Mar 14 '10 at 23:07
There is a diagram of the argument Qiaochu gave here: ams.org/featurecolumn/archive/tsp.html – Douglas Zare Mar 14 '10 at 23:10
But what does it mean to say that the solution has edges that cross? – Harald Hanche-Olsen Mar 14 '10 at 23:22
The natural interpretation is that bob is talking about the Euclidean TSP. – Douglas Zare Mar 14 '10 at 23:40