Titlebar

Export bibliographic data
Literature by the same author
plus on the publication server
plus at Google Scholar

 

The Maximum Scatter TSP on a Regular Grid

Title data

Hoffmann, Isabella ; Kurz, Sascha ; Rambau, Jörg:
The Maximum Scatter TSP on a Regular Grid.
Bayreuth , 2015 . - 6 p.

Official URL: Volltext

Abstract in another language

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 (m x n)-grid. The new algorithm
WEAVE(m,n) takes linear time to compute an optimal tour in
some cases and is asymptotically optimal.

Further data

Item Type: Preprint, postprint, working paper, discussion paper
Keywords: TSP; Maximum Scatter TSP; linear-time algorithm
Institutions of the University: Faculties
Faculties > Faculty of Mathematics, Physics und Computer Science
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Mathematics in Economy
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Mathematics in Economy > Chair Mathematics in Economy - Univ.-Prof. Dr. Jörg Rambau
Research Institutions
Research Institutions > Research Centres
Research Institutions > Research Centres > Forschungszentrum für Modellbildung und Simulation (MODUS)
Result of work at the UBT: Yes
DDC Subjects: 500 Science > 510 Mathematics
Date Deposited: 28 Nov 2015 22:00
Last Modified: 21 Mar 2019 08:19
URI: https://eref.uni-bayreuth.de/id/eprint/23414