Improving TSP tours using dynamic programming over tree decompositions

DOI10.4230/LIPICS.ESA.2017.30MaRDI QIDQ5111717zbMATH OpenOpenAlexFDO

Authors Marek Cygan, Łukasz Kowalik, Arkadiusz Socała

Publication date 27 May 2020

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

zbMATH Keywords

hardness in Plocal searchtreewidthTSPXP algorithm

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)

Abstract: Given a traveling salesman problem (TSP) tour $H$ in graph $G$ a $k$-move is an operation which removes $k$ edges from $H$, and adds $k$ edges of $G$ so that a new tour $H^{\prime }$ is formed. The popular $k$-OPT heuristics for TSP finds a local optimum by starting from an arbitrary tour $H$ and then improving it by a sequence of $k$-moves. Until 2016, the only known algorithm to find an improving $k$-move for a given tour was the naive solution in time $O(n^k)$. At ICALP'16 de Berg, Buchin, Jansen and Woeginger showed an $O(n^{lfloor2/3kfloor+1})$-time algorithm. We show an algorithm which runs in $O(n^{(1/4+epsilo{n}_k)k})$ time, where $limepsilo{n}_k=0$. We are able to show that it improves over the state of the art for every $k=5,ldots,10$. For the most practically relevant case $k=5$ we provide a slightly refined algorithm running in $O(n^{3.4})$ time. We also show that for the $k=4$ case, improving over the $O(n^3)$-time algorithm of de Berg et al. would be a major breakthrough: an $O(n^{3-epsilon})$-time algorithm for any $epsilon>0$ would imply an $O(n^{3-delta})$-time algorithm for the ALL PAIRS SHORTEST PATHS problem, for some $delta>0$.

Recommendations

• Improving TSP Tours Using Dynamic Programming over Tree Decompositions
• Finding a best traveling salesman 4-opt move in the same time as a best 2-opt move
• Fine-grained complexity analysis of two classic TSP variants
• Algorithmic strategies for a fast exploration of the TSP 4-OPT neighborhood
• An improved exact algorithm for TSP in degree-4 graphs

Cites work

• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• A Dynamic Programming Approach to Sequencing Problems
• A method for solving traveling-salesman problems
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• Computer Solutions of the Traveling Salesman Problem
• Dynamic programming meets the principle of inclusion and exclusion
• Finding induced subgraphs via minimal triangulations
• Fine-grained complexity analysis of two classic TSP variants
• How easy is local search?
• Improving TSP tours using dynamic programming over tree decompositions
• New Results on the Old k-opt Algorithm for the Traveling Salesman Problem
• On exact algorithms for treewidth
• On Finding and Verifying Locally Optimal Solutions
• On two techniques of combining branching and treewidth
• Parameterized algorithms
• Pathwidth of cubic graphs and exact algorithms
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Searching the \(k\)-change neighborhood for TSP is W[1]-hard
• Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs
• Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise
• Subcubic equivalences between path, matrix, and triangle problems
• The parameterized complexity of local search for TSP, more refined
• Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic
• Treewidth. Computations and approximations
• Worst-case analysis of a new heuristic for the travelling salesman problem

Cited in

(8)

• Better \(s-t\)-tours by Gao trees
• Finding and counting permutations via CSPs
• Algorithmic strategies for a fast exploration of the TSP 4-OPT neighborhood
• Fine-grained complexity analysis of two classic TSP variants
• Improving TSP Tours Using Dynamic Programming over Tree Decompositions
• Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
• Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP
• Improving TSP tours using dynamic programming over tree decompositions

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 Q5111717)