License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2016.5
URN: urn:nbn:de:0030-drops-62770
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6277/
de Berg, Mark ;
Buchin, Kevin ;
Jansen, Bart M. P. ;
Woeginger, Gerhard
Fine-Grained Complexity Analysis of Two Classic TSP Variants
Abstract
We analyze two classic variants of the Traveling Salesman Problem using the toolkit of fine-grained complexity.
Our first set of results is motivated by the Bitonic tsp problem: given a set of n points in the plane, compute a shortest tour consisting of two monotone chains. It is a classic dynamicprogramming exercise to solve this problem in O(n^2) time. While the near-quadratic dependency of similar dynamic programs for Longest Common Subsequence and Discrete Fréchet Distance has recently been proven to be essentially optimal under the Strong Exponential Time Hypothesis, we show that bitonic tours can be found in subquadratic time. More precisely, we present an algorithm that solves bitonic tsp in O(n*log^2(n)) time and its bottleneck version in O(n*log^3(n)) time. In the more general pyramidal tsp problem, the points to be visited are labeled 1, ..., n and the sequence of labels in the solution is required to have at most one local maximum. Our algorithms for the bitonic (bottleneck) tsp problem also work for the pyramidal tsp problem in the plane.
Our second set of results concerns the popular k-opt heuristic for tsp in the graph setting. More precisely, we study the k-opt decision problem, which asks whether a given tour can be improved by a k-opt move that replaces k edges in the tour by k new edges. A simple algorithm solves k-opt in O(n^k) time for fixed k. For 2-opt, this is easily seen to be optimal. For k = 3 we prove that an algorithm with a runtime of the form ~O(n^{3-epsilon}) exists if and only if All-Pairs Shortest Paths in weighted digraphs has such an algorithm. For general k-opt, it is known that a runtime of f(k)*n^{o(k/log(k))} would contradict the Exponential Time Hypothesis. The results for k = 2, 3 may suggest that the actual time complexity of k-opt is Theta(n^k). We show that this is not the case, by presenting an algorithm that finds the best k-move in O(n^{lfoor 2k/3 rfloor +1}) time for fixed k >= 3. This implies that 4-opt can be solved in O(n^3) time, matching the best-known algorithm for 3-opt. Finally, we show how to beat the quadratic barrier for k = 2 in two important settings, namely for points in the plane and when we want to solve 2-opt repeatedly
BibTeX - Entry
@InProceedings{deberg_et_al:LIPIcs:2016:6277,
author = {Mark de Berg and Kevin Buchin and Bart M. P. Jansen and Gerhard Woeginger},
title = {{Fine-Grained Complexity Analysis of Two Classic TSP Variants}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {5:1--5:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-013-2},
ISSN = {1868-8969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6277},
URN = {urn:nbn:de:0030-drops-62770},
doi = {10.4230/LIPIcs.ICALP.2016.5},
annote = {Keywords: Traveling salesman problem, fine-grained complexity, bitonic tours, k-opt}
}
|
Keywords: |
|
Traveling salesman problem, fine-grained complexity, bitonic tours, k-opt |
|
Collection: |
|
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
23.08.2016 |
