SysNum Seminar: Pr. Tobias Mömke (University of Bremen, Germany) - Wednesday July 11th - 10h meeting room 178 LaBRI

Pr. Tobias Mömke (University of Bremen, Germany) will give a talk on Wednesday 11 July 2018 at the meeting room 178 of LaBRI at 10h on

Maximum Scatter TSP in Doubling Metrics
Laszlo Kozma and Tobias Mömke

Abstract
We study the problem of finding a tour of n points in which every edge is long.
More precisely, we wish to find a tour that visits every point exactly once, maximizing the length of the shortest edge in the tour.
The problem is known as Maximum Scatter TSP, and was introduced by Arkin et al. (SODA 1997), motivated by applications in manufacturing and medical imaging.
Arkin et al. gave a  0.5 -approximation for the metric version of the problem and showed that this is the best possible ratio achievable in polynomial time (assuming P !=NP).
Arkin et al. raised the question of whether a better approximation ratio can be obtained in the Euclidean plane.

We answer this question in the affirmative in a more general setting, by giving
a (1-epsilon)-approximation algorithm for d-dimensional doubling metrics, with running time \tilde{O}(n^{^^3} + 2^(O(K log K))), where K <= ( 13/epsilon)^d.
As a corollary we obtain (i) an efficient polynomial-time approximation scheme (EPTAS) for all constant dimensions d, (ii) a polynomial-time approximation scheme (PTAS) for dimension d = (log log n)/c, for a sufficiently large constant c, and (iii) a PTAS for constant d and epsilon = Omega(1/log log n). Furthermore, we show the dependence on d in our approximation scheme to be essentially optimal, unless Satisfiability can be solved in subexponential time.

Short biography

Tobias Mömke is an interim professor for Theoretical Computer Science at University of Bremen, Germany. He received his doctoral degree in Computer Science from ETH Zurich in 2010. From 2010 to 2015, he held postdoctoral positions at KTH Royal Institute of Technology, Sweden and at Saarland University, Germany. From 2015 to 2017, he was researcher at Saarland University. Tobias Mömke joined University of Bremen in 2017.

His research aims to develop new algorithmic approaches for computationally hard problems. A particular focus of his research is on algorithms for global NP-hard optimization problems such as the traveling salesperson problem or the Steiner tree problem. His work is based on using and developing techniques from combinatorial optimization, with a special focus on linear programming and related advanced methods.

Tobias Mömke was awarded the FOCS 2011 best paper award. He is principal investigator of a research grant awarded by the German Research Foundation (DFG).

Contact: Ralf Klasing, LaBRI