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

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