Dear all,
This is a quick reminder on the next UnRAVeL survey lecture talk Today 12:30 to 14:00, Computer Science Center, Building E2, ground floor, B-IT room 5053.2, given by Britta Peis about "On Train Routing and Length-bounded Disjoint Paths“!
--------------------
Titel:
On Train Routing and Length-bounded Disjoint Paths
Abstract:
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.
(Joint work with Umang Bhaskar, Katharina Eickhoff, Lennart Kauther, Jannik Matuschke, and Laura Vargas Koch)
--------------------
Part of the programme of the research training group UnRAVeL is a series of lectures on the topics of UnRAVeL’s research thrusts algorithms and complexity, verification, logic and languages, and their application scenarios. Each lecture is given by one of the researchers involved in UnRAVeL.
This years topic is "Highlights of UnRAVeL!". As UnRAVeL nears its conclusion, we take this opportunity to reflect on seven years of excellent research. Through nine talks, we invite you to experience the scientific highlights of our RTG, along with its numerous successes, developments, and collaborations.
All interested doctoral researchers and master students are invited to attend the UnRAVeL lecture series 2025 and engage in discussions with researchers and doctoral students.
The overall remaining schedule is as following:
22.05.2025 - Britta Peis - On Train Routing and Length-bounded Disjoint Paths
26.06.2025 - Michael Schaub - Oversmoothing in Graph Neural Networks
03.07.2025 - Sebastian Trimpe - Uncertainty in Learning and Control
10.07.2025 - Christopher Morris - Exploring the Power of Graph Neural Networks in Solving Optimization Problems
17.07.2025 - Christina Büsing - Dealing with Uncertainty Inspired by Health Care – a Robust Optimization Approach
Kind regards,
Jan-Christoph for the organisation committee
