Timeline for Generating uniquely $k$-optimal point sets
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 20, 2016 at 12:52 | comment | added | Joseph O'Rourke | @ManfredWeis: Thanks for those clarifications. | |
| Feb 20, 2016 at 12:38 | comment | added | Manfred Weis | the non-optimal tours in your examples correspond to exchanging $3$ edges of the optimal tour. | |
| Feb 20, 2016 at 12:35 | comment | added | Manfred Weis | The optimal tour through $n$ points is always $n$-optimal; the thing about $k$-optimality is that the tour can't be improved, no matter which subset of $k$ edges is exchanged; that means, that for checking the next set $k$ edges, the previous change has to be reverted. A different aspect is however, that i suspect that in case of a unique $k$-optimal tour it is possible to find the overall optimal tour in $O(n^{k+1})$ time by repeatedly replacing non-optimal subsets of $k$ edges. | |
| Feb 20, 2016 at 12:11 | history | edited | Joseph O'Rourke | CC BY-SA 3.0 |
added 24 characters in body
|
| Feb 20, 2016 at 11:55 | history | answered | Joseph O'Rourke | CC BY-SA 3.0 |