LFCS seminar: Mark de Berg: Finegrained complexity analysis of two classic TSP variants
What 


When 
Mar 08, 2016 from 04:00 PM to 05:00 PM 
Where  IF 4.31/4.33 
Add event to calendar 
vCal iCal 
Finegrained 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 dynamicprogramming exercise to solve this problem in O(n^2) time. While the nearquadratic 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 kOPT heuristic for TSP in the graph setting. More precisely, we study the kOPT decision problem, which asks whether a given tour can be improved by a kOPT move that replaces k edges in the tour by k new edges, for some given constant k. A simple algorithm solves kOPT in O(n^k) time. For 2OPT, this is easily seen to be optimal. For 3OPT we prove that an algorithm with a runtime of the form O*(n^{3\eps}) exists if and only if ALLPAIRS SHORTEST PATHS in weighted digraphs has such an algorithm. For general kOPT, 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 kOPT is \Theta(n^k). We show that this is not the case, by presenting an algorithm that finds the best kmove in O(n^{\floor{2k/3} + 1}) time. Finally, we show how to beat the quadratic barrier for 2OPT in two important settings, namely for points in the plane and when we want to solve 2OPT 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 peerreviewed 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 ComputationalGeometry Steering Committee.