The maximum scatter TSP on a regular grid

DOI10.1007/978-3-319-42902-1_9MaRDI QIDQ4596195zbMATH OpenOpenAlexFDO

Authors Isabella Hoffmann, Sascha Kurz, Jörg Rambau

Publication date 1 December 2017

Published in Operations Research Proceedings (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.02054, https://epub.uni-bayreuth.de/2524/1/Hoffmann%2BKurz%2BRambau_preprint_The_Maximum_Scatter%20TSP_on_a_Regular_Grid.pdf

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Abstract: In the maximum scatter traveling salesman problem the objective is to find a tour that maximizes the shortest distance between any two consecutive nodes. This model can be applied to manufacturing processes, particularly laser melting processes. We extend an algorithm by Arkin et al. that yields optimal solutions for nodes on a line to a regular $mimesn$-grid. The new algorithm $extscWeave(m,n)$ takes linear time to compute an optimal tour in some cases. It is asymptotically optimal and a $fracsqrt105$-approximation for the $3imes4$-grid, which is the worst case.

Recommendations

• On the Maximum Scatter Traveling Salesperson Problem
• New approximation results for the maximum scatter TSP
• The traveling salesman problem on grids with forbidden neighborhoods
• Approximation algorithms for lawn mowing and milling
• Maximum Scatter TSP in Doubling Metrics

Cited in

(6)

• The traveling salesman problem on grids with forbidden neighborhoods
• New approximation results for the maximum scatter TSP
• On the Maximum Scatter Traveling Salesperson Problem
• Maximum Scatter TSP in Doubling Metrics
• Perturbation analysis of practical algorithms for the maximum scatter travelling salesman problem
• A survey on approximability of traveling salesman problems using the TSP-T3CO definition scheme

This page was built for publication: The maximum scatter TSP on a regular grid

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