Maximum Scatter TSP in Doubling Metrics

DOI10.1137/1.9781611974782.10zbMATH Open1411.68197arXiv1512.02963OpenAlexW2471508234MaRDI QIDQ4575744FDOQ4575744

Authors: László Kozma, Tobias Mömke 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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 $PeqNP$). 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 $$, where $Kleqleft(frac13epsilonight{)}^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=loglogn/c$, for a sufficiently large constant $c$, and (iii) a PTAS for constant $d$ and $epsilon=Omega(1/loglogn)$. Furthermore, we show the dependence on $d$ in our approximation scheme to be essentially optimal, unless Satisfiability can be solved in subexponential time.

Full work available at URL: https://arxiv.org/abs/1512.02963

Recommendations

• New approximation results for the maximum scatter TSP
• The maximum scatter TSP on a regular grid
• On the Maximum Scatter Traveling Salesperson Problem
• Better approximations for max TSP
• Algorithms – ESA 2005
• scientific article; zbMATH DE number 2079395
• Approximating Multi-criteria Max-TSP
• An improved approximation algorithm for the maximum TSP
• An improved randomized approximation algorithm for Max TSP
• Improved approximation algorithms for metric MaxTSP

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cited In (9)

• Reducing curse of dimensionality: improved PTAS for TSP (with neighborhoods) in doubling metrics
• Efficient PTAS for the maximum traveling salesman problem in a metric space of fixed doubling dimension
• A Modern View on Stability of Approximation
• Many Visits TSP Revisited
• The traveling salesman problem on grids with forbidden neighborhoods
• Many-visits TSP revisited
• A 3/2-Approximation for the Metric Many-Visits Path TSP
• New approximation results for the maximum scatter TSP
• The maximum scatter TSP on a regular grid

This page was built for publication: Maximum Scatter TSP in Doubling Metrics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575744)