| Mark de Berg |
| Tue 08 Mar 2016, 16:00 - 17:00 |
| IF 4.31/4.33 |
If you have a question about this talk, please contact: Rik Sarkar (rsarkar)
Fine-grained complexity analysis of two classic TSP variants
(joint work with Kevin Buchin, Bart Jansen, and Gerhard Woeginger)
Abstract:
In this talk I will discuss new results on two classic TSP variants.
The first set of results concerns BITONIC TSP: given a set of n points in the plane, compute a shortest tour consisting of two monotone chains. It is a classic dynamic-programming 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 FRECHET 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.
The 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, for some given constant k. A simple algorithm solves k-OPT in O(n^k) time. For 2-OPT, this is easily seen to be optimal. For 3-OPT we prove that an algorithm with a runtime of the form O*(n^{3-\eps}) 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) \cdot 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^{\floor{2k/3} + 1}) time. Finally, we show how to beat the quadratic barrier for 2-OPT in two important settings, namely for points in the plane and when we want to solve 2-OPT repeatedly.
Speaker bio: Mark de Berg received an M.Sc. in computer science from Utrecht University (the Netherlands) in 1988, and he received a Ph.D. from the same university in 1992. Currently he is a full professor at the TU Eindhoven. His main research interest is in algorithms and data structures, in particular for spatial data. He is (co-)author of two books on computational geometry and he has published over 200 peer-reviewed papers in journals and conferences. Mark de Berg was on the program committee of many international conferences in the field, and he serves on the editorial board of three journals. He has been chair of the Steering Committee of the European Symposium on Algorithms, and is currently a member of the international Computational-Geometry Steering Committee.