文章基本信息

标题：Improving TSP Tours Using Dynamic Programming over Tree Decompositions
本地全文：下载
作者：Marek Cygan ; Lukasz Kowalik ; Arkadiusz Socala 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：87
页码：30:1-30:14
DOI：10.4230/LIPIcs.ESA.2017.30
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：TSP; treewidth; local search; XP algorithm; hardness in P