Fine-grained Complexity Analysis of Two Classic TSP Variants

DOI10.1145/3414845MaRDI QIDQ5028342zbMATH OpenOpenAlexFDO

Authors Kevin Buchin, Bart M. P. Jansen, Gerhard J. Woeginger, Mark de Berg

Publication date 8 February 2022

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

Full work available at URL https://research.tue.nl/nl/publications/783580a6-48fc-4ea1-9889-cded5248efe0

zbMATH Keywords

traveling salesman problem\(k\)-OPTfine-grained complexitybitonic TSP

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Recommendations

• Fine-grained complexity analysis of two classic TSP variants
• Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP
• TSP heuristics: domination analysis and complexity
• The parameterized complexity of local search for TSP, more refined
• The parameterized complexity of local search for TSP, more refined
• Analysis of a near-metric TSP approximation algorithm
• Complexity analysis and optimization of the shortest path tour problem
• The parallel complexity of TSP heuristics
• Fat computational complexity and heuristic design for the TSP
• scientific article; zbMATH DE number 5859273

Cited in

(5)

• On polynomial kernels for traveling salesperson problem and its generalizations
• An optimal algorithm for \(L_1\) shortest paths in unit-disk graphs
• Hybrid genetic search for the CVRP: open-source implementation and SWAP* neighborhood
• A k-swap local search for makespan scheduling
• Euclidean TSP in narrow strips

This page was built for publication: Fine-grained Complexity Analysis of Two Classic TSP Variants

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