at Google ScholarTitle data
Hoffmann, Isabella ; Kurz, Sascha ; Rambau, Jörg:
The Maximum Scatter TSP on a Regular Grid.
Bayreuth
,
2015
. - 6 p.
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 |
|---|---|
| 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 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 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 |