Maximum Scatter TSP in Doubling Metrics

DOI10.1137/1.9781611974782.10MaRDI QIDQ4575744zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cited in

(9)

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

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)