2026-08-17T14:14:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7853 2024-03-06T10:41:18Z ddc:004 open_access

Improving TSP Tours Using Dynamic Programming over Tree Decompositions Cygan, Marek Kowalik, Lukasz Socala, Arkadiusz TSP treewidth local search XP algorithm hardness in P 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' is formed. The popular k-opt heuristic 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^{floor(2/3k)+1})-time algorithm. We show an algorithm which runs in O(n^{(1/4 + epsilon_k)k}) time, where lim_{k -> infinity} epsilon_k = 0. It improves over the state of the art for every k >= 5. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marek Cygan and Lukasz Kowalik and Arkadiusz Socala 2017 Is Part Of LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2017.30 urn:nbn:de:0030-drops-78539 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.30 eng https://creativecommons.org/licenses/by/3.0/legalcode