Personal tools
You are here: Home CG seminar Spring 2017 Maximum Scatter TSP in doubling metrics
« June 2017 »
Log in

Forgot your password?

Maximum Scatter TSP in doubling metrics

Wednesday, March 29th, 2017 16:10

Schreiber 309


Maximum Scatter TSP in doubling metrics

Laszlo Kozma, TAU


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'97), motivated by applications in manufacturing
and medical imaging. Arkin et al. gave a 2-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 geometric settings, such as the Euclidean plane. We answer this question in the affirmative in a more general setting, by giving an efficient polynomial time approximation scheme for d-dimensional doubling metrics.

Joint work with Tobias Mömke.
Document Actions