Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP

DOI10.4230/LIPIcs.ESA.2019.23OpenAlexW4327812391MaRDI QIDQ5075760

Łukasz Kowalik, Bart M. P. Jansen, Yoichi Iwata, Édouard Bonnet

Publication date: 11 May 2022

Full work available at URL: https://arxiv.org/abs/1908.09325

zbMATH Keywords

traveling salesman problembounded degree\(k\)-OPT

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Uses Software

• LKH

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The parameterized complexity of local search for TSP, more refined
• Finding and counting given length cycles
• Searching the \(k\)-change neighborhood for TSP is W[1-hard]
• General \(k\)-opt submoves for the Lin-Kernighan TSP heuristic
• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Fine-grained complexity analysis of two classic TSP variants
• Improving TSP Tours Using Dynamic Programming over Tree Decompositions.
• The traveling-salesman problem and minimum spanning trees: Part II
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem

This page was built for publication: Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP