Fine-grained complexity of k-OPT in bounded-degree graphs for solving TSP
- Édouard Bonnet,
- Yoichi Iwata,
- ,
- Łukasz Kowalik
- École Normale Supérieure de Lyon,
- National Institute of Informatics,
- ,
- University of Warsaw
Output:
Contribution to journal
Article
Academic
Open access
Information
Output type
Output:
Contribution to journal
Article
Academic
Original language
EnglishArticle number
1908.09325v2Journal (Volume, Issue Number)
arXiv (Volume 2019)Publication milestones
- Published - 2019
Publication status
Published - 2019
Abstract
Local search is a widely-employed strategy for finding good solutions to Traveling Salesman Problem. We analyze the problem of determining whether the weight of a given cycle can be decreased by a popular k-opt move. Earlier work has shown that (i) assuming the Exponential Time Hypothesis, there is no algorithm to find an improving k-opt move in time f(k)no(k/logk) for any function f, while (ii) it is possible to improve on the brute-force running time of O(nk) and save linear factors in the exponent. Modern TSP heuristics show that very good global solutions can already be reached using only the top-O(1) most promising edges incident to each vertex. Motivated by this, we study the problem of finding an improving k-move in bounded degree graphs, presenting new algorithms and conditional lower bounds. We show that the aforementioned ETH lower bound also holds for graphs of maximum degree three, but that in bounded-degree graphs the best improving k-move can be found in time O(n23k/135+o(k)). This improves upon the best-known bounds for general graphs. Due to its practical importance, we devote special attention to the range of k in which improving k-moves in bounded-degree graphs can be found in quasi-linear time. For k≤7, we give quasi-linear time algorithms for general weights. For k=8 we obtain a quasi-linear time algorithm for polylogarithmic weights. On the other hand, based on established fine-grained complexity hypotheses, we prove that the k=9 case does not admit quasi-linear time algorithms. Hence we fully characterize the values of k for which quasi-linear time algorithms exist for polylogarithmic weights on bounded-degree graphs. As a byproduct, we show a new bound on pathwidth of even graphs which results in improved running time bounds for counting k-vertex paths and cycles.
Documents and Links
Final published version, 1.08 MB
Metrics
Metrics
Download statistics
Download count
450
