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
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Jun 26, 2015 at 13:33 | comment | added | Joseph O'Rourke | @GordonRoyle: Sorry, I didn't follow your link before composing my answer. | |
| Jun 26, 2015 at 13:29 | comment | added | Gordon Royle | @Dominic... Too late, someone else has already done so! | |
| Jun 26, 2015 at 11:41 | vote | accept | Dominic van der Zypen | ||
| Jun 26, 2015 at 11:40 | answer | added | Joseph O'Rourke | timeline score: 15 | |
| Jun 26, 2015 at 11:31 | comment | added | Dominic van der Zypen | Thanks - can you make this into an answer, please? | |
| Jun 26, 2015 at 10:03 | comment | added | Gordon Royle | See the answer to this question: cstheory.stackexchange.com/questions/18307/… | |
| Jun 26, 2015 at 7:01 | comment | added | individ | Should the task of paraphrase. Takes a random number of points $n$ they randomly have on the plane. And with some random points start to crawl by this algorithm outperforming all points. And need to know the mathematical expectation of how many times it is not effective? The number of points does not play any role. | |
| Jun 26, 2015 at 6:48 | history | edited | Dominic van der Zypen | CC BY-SA 3.0 |
added 130 characters in body
|
| Jun 26, 2015 at 6:48 | comment | added | Dominic van der Zypen | So what is the biggest factor nearest neighbor trip vs best trip can take? | |
| Jun 26, 2015 at 6:46 | comment | added | individ | Does not exist. It all depends on the position of the points. You can even choose the location that this algorithm is optimal. | |
| Jun 26, 2015 at 6:35 | history | asked | Dominic van der Zypen | CC BY-SA 3.0 |