3 papers
cs.DS2026
Approximation Algorithms for Graphic Multi-Depot TSP and Graphic Multi-Path TSP
Niklas Dahlmeier, Raoul Luqué, Philipp Pabst +1
We give improved approximation algorithms for two graphic TSP variants. First, we consider Multi-Depot TSP on graphic instances. In this variant, we are given an undirected graph w…
cs.DS2025
Approximating Graphic Multi-Path TSP and Graphic Ordered TSP
Morteza Alimi, Niklas Dahlmeier, Tobias Mömke +2
The path version of the Traveling Salesman Problem is one of the most well-studied variants of the ubiquitous TSP. Its generalization, the Multi-Path TSP, has recently been used in…
cs.DS2025
On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem
Umang Bhaskar, Katharina Eickhoff, Lennart Kauther +3
In train routing, the headway is the minimum distance that must be maintained between successive trains for safety and robustness. We introduce a model for train routing that requi…