2017/03/16 by Marek Cygan, Cygan, Marek, Łukasz Kowalik +3 · 2 citations
Computer Science · Engineering · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Vehicle Routing Optimization Methods
paper · doi:10.48550/arxiv.1703.05559
openalex publication_date 2017/03/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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(nk). At ICALP'16 de Berg, Buchin, Jansen and Woeginger showed an O(n\lfloor 2/3k \rfloor+1)-time algorithm. We show an algorithm which runs in O(n(1/4+εk)k) time, where lim εk = 0. We are able to show that it improves over the state of the art for every k=5,…,10. For the most practically relevant case k=5 we provide a slightly refined algorithm running in O(n3.4) time. We also show that for the k=4 case, improving over the O(n3)-time algorithm of de Berg et al. would be a major breakthrough: an O(n3-ε)-time algorithm for any ε>0 would imply an O(n3-δ)-time algorithm for the ALL PAIRS SHORTEST PATHS problem, for some δ>0.