For bounded-degree TSP instances, the best improving k-move can be found in time O(n^{0.1704k+o(k)}), and improving k-moves are quasi-linear for k≤8 (k=8 with polylog weights) and conditionally not for k=9.
Title resolution pending
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
fields
cs.DS 1years
2019 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP
For bounded-degree TSP instances, the best improving k-move can be found in time O(n^{0.1704k+o(k)}), and improving k-moves are quasi-linear for k≤8 (k=8 with polylog weights) and conditionally not for k=9.