Timeline for Characterization of greedy TSPs?
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 21, 2022 at 4:20 | comment | added | Manfred Weis | any set of points that samples a piecewise smooth closed curve dense enough will do where *dense enough" means that the Euclidean distance between neighboring points is e.g. smaller then the minimum distance betwen a point of the curve's Voronoi diagram to a point on the curve. Actually twice that distance may suffice. | |
| Feb 19, 2022 at 9:28 | answer | added | Manfred Weis | timeline score: 1 | |
| Feb 12, 2022 at 14:27 | history | edited | Joseph O'Rourke | CC BY-SA 4.0 |
Made clear using Euclidean distance.
|
| Feb 12, 2022 at 0:24 | comment | added | Sam Hopkins | Yeah, I get that, was just a comment. My (random) guess would be that it would be hard to describe the TSP instances where nearest neighbor is optimal. | |
| Feb 12, 2022 at 0:23 | comment | added | Joseph O'Rourke | Thanks, @SamHopkins. I am less interested in the algorithmic issues as I am in understanding the shape of the point sets that can be greedily TSP'ed, so-to-speak. | |
| Feb 11, 2022 at 23:58 | comment | added | Sam Hopkins | See en.wikipedia.org/wiki/… for some discussion of the nearest neighbor approach to TSP. (Note that the minimum spanning tree-based algorithm is also quite simple, but does better.) | |
| Feb 11, 2022 at 23:53 | history | asked | Joseph O'Rourke | CC BY-SA 4.0 |