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…