Matthias Mnich - Time- and Space-Optimal Algorithms for the Many-Visits TSP

Explore an advanced lecture on the many-visits traveling salesperson problem (MV-TSP) and its algorithmic solutions. Delve into the intricacies of this combinatorial optimization problem, which requires finding an optimal tour of cities with multiple visits. Learn about the applications of MV-TSP in scheduling, geometric approximation, and graph theory. Examine the Cosmadakis-Papadimitriou algorithm and its limitations, then discover a groundbreaking single-exponential time algorithm with output-linear space. Understand the significance of this improvement in terms of time and space complexity, and its implications for solving large-scale MV-TSP instances. Follow the lecturer's step-by-step explanation of the problem formulation, algorithm development, and complexity analysis. Gain insights into advanced topics such as single-machine scheduling, TSP formulations, and runtime improvements. This in-depth exploration of cutting-edge algorithms for the MV-TSP is ideal for researchers and practitioners in combinatorial optimization and computer science.

Intro
Single-machine scheduling with few job classes
A TSP formulation
Applications
Previous work
The algorithm by Cosmadakis & Papadimitriou, SICOMP 1984
Example
A first simple algorithm
Solution
Formulating the improved algorithm
The improved algorithm / 2
Complexity analysis
Final run time improvements / 1
Summary