Timeline for Generalized Euclidean TSP
Current License: CC BY-SA 2.5
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 28, 2017 at 0:40 | history | edited | François G. Dorais |
edited tags
|
|
| Mar 1, 2011 at 22:57 | vote | accept | John Gunnar Carlsson | ||
| Mar 1, 2011 at 22:23 | answer | added | Peter Shor | timeline score: 10 | |
| Mar 1, 2011 at 19:26 | comment | added | Joseph O'Rourke | There is a transformation of the GTSP to the TSP, the Laporte-Semet transformation. It doubles the number of vertices. Perhaps this could be a route to obtain a result? [G. Laporte, F. Semet, "Computational evaluation of a transformation procedure for the symmetric generalized traveling salesman problem," INFOR (37) 1999 114–120.] | |
| Mar 1, 2011 at 19:23 | comment | added | Or Zuk | Very interesting. A variant where the sets are not predefined, but rather you look for the $n$ points giving you the shortest path (out of the $nk$) was considered by David Aldous but is also open: stat.berkeley.edu/~aldous/Research/OP/simTSP.html | |
| Mar 1, 2011 at 18:55 | history | edited | John Gunnar Carlsson | CC BY-SA 2.5 |
Clarified "asymptotic"
|
| Mar 1, 2011 at 18:53 | comment | added | John Gunnar Carlsson | I'm assuming that $k$ is fixed, and we're looking at the behavior as $n$ goes to infinity. | |
| Mar 1, 2011 at 18:40 | comment | added | camomille | What is the link between $k$ and $n$ ? | |
| Mar 1, 2011 at 17:59 | history | edited | John Gunnar Carlsson | CC BY-SA 2.5 |
Completed BHH acronym
|
| Mar 1, 2011 at 17:58 | comment | added | John Gunnar Carlsson | Beardwood-Halton-Hammersley. It says that, when $k=1$ in my problem (i.e. the shortest path through $n$ uniformly sampled points), the path length scales with $\sqrt{n}$: myweb.lsbu.ac.uk/~whittyr/MathSci/TheoremOfTheDay/OR/BHH/… | |
| Mar 1, 2011 at 17:55 | comment | added | Gil Kalai | Looks like a great question, but what is BHH theorem? | |
| Mar 1, 2011 at 17:26 | history | asked | John Gunnar Carlsson | CC BY-SA 2.5 |