Improving TSP Tours Using Dynamic Programming over Tree Decompositions

DOI10.1145/3341730zbMath1442.68285MaRDI QIDQ4973050

Marek Cygan, Łukasz Kowalik, Arkadiusz Socała

Publication date: 2 December 2019

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7853/

zbMATH Keywords

local search; treewidth; traveling salesman problem; k-OPT

Mathematics Subject Classification ID

68W40: Analysis of algorithms

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

90C39: Dynamic programming

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)