in the repository
Title data
Hoffmann, Isabella ; Kurz, Sascha ; Rambau, Jörg:
The Maximum Scatter TSP on a Regular Grid.
Bayreuth
,
2015
. - 6 S.
![[thumbnail of Hoffmann+Kurz+Rambau_preprint_The_Maximum_Scatter TSP_on_a_Regular_Grid.pdf]](https://epub.uni-bayreuth.de/style/images/fileicons/application_pdf.png) |
|
||||||||
|
Download (333kB)
|
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 (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 |
|---|---|
| Additional notes (visible to public): | erschienen in:
Doerner, Karl Franz ; Ljubic, Ivana ; Pflug, Georg ; Tragler, Gernot , Gesellschaft für Operations-Research (Hrsg.): Operations Research Proceedings 2015. - Cham : Springer , 2017 . - S. 63-70 ISBN 978-3-319-42901-4 DOI: https://doi.org/10.1007/978-3-319-42902-1_9 |
| Keywords: | TSP; Maximum Scatter TSP; linear-time algorithm |
| DDC Subjects: | 500 Science > 510 Mathematics |
| Institutions of the University: | Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Mathematical Economics > Chair Mathematical Economics - Univ.-Prof. Dr. Jörg Rambau 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 Mathematical Economics |
| Language: | English |
| Originates at UBT: | Yes |
| URN: | urn:nbn:de:bvb:703-epub-2524-2 |
| Date Deposited: | 25 Nov 2015 09:40 |
| Last Modified: | 28 May 2021 10:11 |
| URI: | https://epub.uni-bayreuth.de/id/eprint/2524 |
Download Statistics