Welcome to MathOverflow

Question

0

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

flag	asked Mar 14 2010 at 22:45 bob 9●1

9

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 2010 at 22:51

3

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 2010 at 23:07

There is a diagram of the argument Qiaochu gave here: ams.org/featurecolumn/archive/tsp.html – Douglas Zare Mar 14 2010 at 23:10

But what does it mean to say that the solution has edges that cross? – Harald Hanche-Olsen Mar 14 2010 at 23:22

The natural interpretation is that bob is talking about the Euclidean TSP. – Douglas Zare Mar 14 2010 at 23:40

lhf · Answer 1 · 2010-03-14 23:35:50Z UTC

6

I've answered this in http://stackoverflow.com/questions/2444125/crossing-edges-in-the-travelling-salesman-problem/2444288#2444288.

answered Mar 14 2010 at 23:35

lhf
1,875●1●8●19

lemire · Answer 2 · 2011-12-07 05:16:53Z UTC

0

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)

answered Dec 7 2011 at 5:16

lemire
175●1●1●6

2

But the hamming distance satisfies the triangle inequality. – Suresh Venkat Dec 7 2011 at 5:52

Travelling Salesman Problem

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.