Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

closed as off-topic by Ricardo Andrade, Lucia, Chris Godsil, Ryan Budney, Stefan Kohl Apr 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

2 Answers 2

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)

share|improve this answer
But the hamming distance satisfies the triangle inequality. –  Suresh Venkat Dec 7 '11 at 5:52

Not the answer you're looking for? Browse other questions tagged or ask your own question.