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.
In: Doerner, Karl Franz ; Ljubic, Ivana ; Pflug, Georg ; Tragler, Gernot , Gesellschaft für Operations-Research (ed.): Operations Research Proceedings 2015. - Cham : Springer , 2017 . - pp. 63-70
ISBN 978-3-319-42901-4
DOI: https://doi.org/10.1007/978-3-319-42902-1_9

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: Article in a book
Refereed: Yes
Keywords: TSP; Maximum Scatter TSP; linear-time algorithm
Institutions of the University: 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
Faculties
Faculties > Faculty of Mathematics, Physics und Computer Science
Result of work at the UBT: Yes
DDC Subjects: 000 Computer Science, information, general works > 004 Computer science
500 Science > 510 Mathematics
Date Deposited: 17 Jul 2017 09:41
Last Modified: 17 Jul 2017 09:41
URI: https://eref.uni-bayreuth.de/id/eprint/38461