Timeline for Travelling Salesman Problem: Can the nearest neighbor algorithm be $n$ times longer than the optimal solution?
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 29, 2015 at 7:05 | comment | added | Dominic van der Zypen | Thanks for the picture @JosephO'Rourke - very intuitive!! | |
| Jun 27, 2015 at 11:51 | history | edited | Joseph O'Rourke | CC BY-SA 3.0 |
added 401 characters in body
|
| Jun 27, 2015 at 10:47 | comment | added | Manfred Weis | @JosephO'Rourke do you have a picture of a worst-case instance? I couldn't find one in the cited paper. | |
| Jun 26, 2015 at 14:52 | comment | added | TonyK | You're still saying No... | |
| Jun 26, 2015 at 14:51 | history | edited | Joseph O'Rourke | CC BY-SA 3.0 |
added 1 character in body
|
| Jun 26, 2015 at 14:44 | history | edited | Joseph O'Rourke | CC BY-SA 3.0 |
added 228 characters in body
|
| Jun 26, 2015 at 14:36 | comment | added | Joseph O'Rourke | @BillBradley: Good point. In the Johnson-McGeoch experimental results (p.15), they distinguish between "random Euclidean instances" and "random distance matrices." The former approach a fixed 25% longer than the K-H lower bound. I will correct my answer. | |
| Jun 26, 2015 at 14:27 | comment | added | Bill Bradley | Doesn't the paper refer to the metric TSP, whereas the OP is asking about the special case of TSP in the plane? | |
| Jun 26, 2015 at 14:02 | history | edited | Joseph O'Rourke | CC BY-SA 3.0 |
added 105 characters in body
|
| Jun 26, 2015 at 13:59 | comment | added | Joseph O'Rourke | @TonyK: Oh, you are right, I was mixing $n$ with $N$. :-) | |
| Jun 26, 2015 at 13:44 | comment | added | TonyK | Doesn't that mean that the answer to the first question is Yes? Given $n$, we can always choose $N$ so that $0.5(\lceil \log_2N\rceil+1) > n$. | |
| Jun 26, 2015 at 11:41 | vote | accept | Dominic van der Zypen | ||
| Jun 26, 2015 at 11:40 | history | answered | Joseph O'Rourke | CC BY-SA 3.0 |