at Google ScholarTitle 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
Related URLs
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 Mathematical Economics 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 |
| 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: | 28 May 2021 10:10 |
| URI: | https://eref.uni-bayreuth.de/id/eprint/38461 |