## Title 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 |