2026-07-23T04:53:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24502 2025-12-16T14:00:03Z ddc:004 open_access

On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem Bhaskar, Umang Eickhoff, Katharina Kauther, Lennart Matuschke, Jannik Peis, Britta Vargas Koch, Laura Train Routing Scheduling Approximation Algorithms Flows over Time Min-Max Disjoint Paths 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 requires a fixed headway to be maintained between trains, and study the problem of minimizing the makespan, i.e., the arrival time of the last train, in a single-source single-sink network. For this problem, we first show that there exists an optimal solution where trains move in convoys - that is, the optimal paths for any two trains are either the same or are arc-disjoint. Via this insight, we are able to reduce the approximability of our train routing problem to that of the min-max disjoint paths problem, which asks for a collection of disjoint paths where the maximum length of any path in the collection is as small as possible. While min-max disjoint paths inherits a strong inapproximability result on directed acyclic graphs from the multi-level bottleneck assignment problem, we show that a natural greedy composition approach yields a logarithmic approximation in the number of disjoint paths for series-parallel graphs. We also present an alternative analysis of this approach that yields a guarantee depending on how often the decomposition tree of the series-parallel graph alternates between series and parallel compositions on any root-leaf path. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Umang Bhaskar and Katharina Eickhoff and Lennart Kauther and Jannik Matuschke and Britta Peis and Laura Vargas Koch 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.34 urn:nbn:de:0030-drops-245029 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.34 eng https://creativecommons.org/licenses/by/4.0/legalcode