The many-visits traveling salesperson problem (MV-TSP) asks for an optimal tour that visits each city a prescribed number of times. Travel costs may be asymmetric and visiting a city twice in a row may incur a non-zero cost. The fastest known exact algorithm is due to Cosmadakis and Papadimitriou (SICOMP, 1984) and has time and space complexity super-exponential in the number of cities. We propose an exact algorithm that runs in single-exponential time and requires only polynomial space, which is, assuming the ETH, asymptotically optimal.

Speaker Bio

Roland Vincze is a PhD student at Maastricht University, The Netherlands and he is on a research visit at SUTD. Roland’s research interests are in theoretical computer science, graph theory and operations research. Before joining the Maastricht University, he did his studies at the Budapest University of Technology and Economics in Hungary.

For more information about the ESD Seminars Series, please contact Karthyek Murthy at karthyek_murthy@sutd.edu.sg.