Improving TSP Tours Using Dynamic Programming over Tree Decompositions

DOI10.1145/3341730zbMath1442.68285OpenAlexW2980171939WikidataQ127155580 ScholiaQ127155580MaRDI 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 searchtreewidthtraveling salesman problemk-OPT

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Dynamic programming (90C39) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Circular Jaccard distance based multi-solution optimization for traveling salesman problems

This page was built for publication: Improving TSP Tours Using Dynamic Programming over Tree Decompositions