Personal tools
You are here: Home CG seminar Spring 2017 Maximum Scatter TSP in doubling metrics
« October 2017 »
October
SuMoTuWeThFrSa
1234567
891011121314
15161718192021
22232425262728
293031
Log in


Forgot your password?
 

Maximum Scatter TSP in doubling metrics

Wednesday, March 29th, 2017 16:10

Schreiber 309

underline

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.
Document Actions