# Maximum Scatter TSP in doubling metrics

### Wednesday, March 29th, 2017 16:10

### Schreiber 309

### Maximum Scatter TSP in doubling metrics

### Laszlo Kozma, TAU

### 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'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.

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.