 |
Universität Augsburg
|
|
|
Universität Augsburg
|
|
Professor Dr. Tobias Mömke
Universität Augsburg, Institut für Informatik
spricht am
Dienstag, 17. Juni 2025
um
15:45 Uhr
im
Raum 1007 (L1)
über das Thema:
| Abstract: |
| In this talk, I will present recent advances in approximation algorithms for routing problems with multiple terminals — including Ordered TSP, Multipath TSP, and Capacitated Vehicle Routing with multiple depots, as well as their prize-collecting variants. These problems turn out to be amenable to a set of emerging algorithmic techniques based on a preflow-splitting result by Bang-Jensen, Frank, and Jackson. I will survey these new results with an emphasis on the underlying methods: LP relaxations combined with flow decompositions, randomized terminal sampling (e.g., via variants of the Bridge Lemma of Byrka et al.), and combinatorial postprocessing techniques such as pruning and cycle merging. These tools not only yield improved approximation guarantees across diverse problem settings but also suggest a unifying framework for addressing a broader class of vehicle routing and network design problems with structured terminal constraints. |
| Hierzu ergeht herzliche Einladung. |
| Prof. Dr. Elisabeth Gaar |