Timeline for Travelling Salesman Problem [closed]
Current License: CC BY-SA 2.5
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 14, 2014 at 23:06 | history | closed |
Ricardo Andrade Lucia Chris Godsil Ryan Budney Stefan Kohl♦ |
Not suitable for this site | |
| Apr 14, 2014 at 21:14 | review | Close votes | |||
| Apr 14, 2014 at 23:06 | |||||
| Dec 7, 2011 at 5:16 | answer | added | lemire | timeline score: 0 | |
| Mar 14, 2010 at 23:40 | comment | added | Douglas Zare | The natural interpretation is that bob is talking about the Euclidean TSP. | |
| Mar 14, 2010 at 23:35 | answer | added | lhf | timeline score: 6 | |
| Mar 14, 2010 at 23:22 | comment | added | Harald Hanche-Olsen | But what does it mean to say that the solution has edges that cross? | |
| Mar 14, 2010 at 23:10 | comment | added | Douglas Zare | There is a diagram of the argument Qiaochu gave here: ams.org/featurecolumn/archive/tsp.html | |
| Mar 14, 2010 at 23:07 | comment | added | Joseph Malkevitch | 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. | |
| Mar 14, 2010 at 22:51 | comment | added | Qiaochu Yuan | 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. | |
| Mar 14, 2010 at 22:45 | history | asked | bob | CC BY-SA 2.5 |