Improving TSP Tours Using Dynamic Programming over Tree Decompositions

DOI10.1145/3341730MaRDI QIDQ4973050zbMATH OpenOpenAlexWikidataFDO

Authors 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

k-OPTlocal searchtraveling salesman problemtreewidth

Mathematics Subject Classification ID

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

Recommendations

• Improving TSP tours using dynamic programming over tree decompositions
• An Effective Tour Construction and Improvement Procedure for the Traveling Salesman Problem
• Dynamic programming and planarity: improved tree-decomposition based algorithms
• scientific article; zbMATH DE number 836777
• An improved approximation algorithm for the traveling tournament problem
• An Improved Approximation Algorithm for the Traveling Tournament Problem
• Dynamic programming and the graphical traveling salesman problem
• A modification of the dynamic programming method for the travelling-salesman problem
• An improved approximation algorithm for the maximum TSP
• On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees

Cited in

(8)

• Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm
• A comparison of algorithms for finding an efficient theme park tour
• Better \(s-t\)-tours by Gao trees
• Circular Jaccard distance based multi-solution optimization for traveling salesman problems
• Fine-grained complexity analysis of two classic TSP variants
• Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP
• Improving TSP tours using dynamic programming over tree decompositions
• On polynomial kernels for traveling salesperson problem and its generalizations

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4973050)