A time- and space-optimal algorithm for the many-visits TSP

DOI10.1137/1.9781611975482.106MaRDI QIDQ5236290zbMATH OpenOpenAlexFDO

Authors André Berger, László Kozma, Matthias Mnich, Roland Vincze

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611975482.106

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27)

Recommendations

• Time- and space-optimal algorithm for the many-visits TSP
• Many-visits TSP revisited
• A 3/2-Approximation for the Metric Many-Visits Path TSP
• scientific article; zbMATH DE number 4053381
• Approximating asymmetric TSP in exponential time

Cited in

(6)

• High multiplicity asymmetric traveling salesman problem with feedback vertex set and its application to storage/retrieval system
• Many-visits TSP revisited
• Domino sequencing: scheduling with state-based sequence-dependent setup times
• Time- and space-optimal algorithm for the many-visits TSP
• A 3/2-Approximation for the Metric Many-Visits Path TSP
• Approximate Counting of k-Paths: Deterministic and in Polynomial Space

This page was built for publication: A time- and space-optimal algorithm for the many-visits TSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236290)