Search Results

Documents authored by Eickhoff, Katharina

Document
DOI: 10.4230/LIPIcs.ESA.2025.34
On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem

Authors: Umang Bhaskar, Katharina Eickhoff, Lennart Kauther, Jannik Matuschke, Britta Peis, and Laura Vargas Koch

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

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.
Cite as

Umang Bhaskar, Katharina Eickhoff, Lennart Kauther, Jannik Matuschke, Britta Peis, and Laura Vargas Koch. On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhaskar_et_al:LIPIcs.ESA.2025.34,
  author =	{Bhaskar, Umang and Eickhoff, Katharina and Kauther, Lennart and Matuschke, Jannik and Peis, Britta and Vargas Koch, Laura},
  title =	{{On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{34:1--34:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.34},
  URN =		{urn:nbn:de:0030-drops-245029},
  doi =		{10.4230/LIPIcs.ESA.2025.34},
  annote =	{Keywords: Train Routing, Scheduling, Approximation Algorithms, Flows over Time, Min-Max Disjoint Paths}
}
Document
DOI: 10.4230/DagRep.12.5.92
Dynamic Traffic Models in Transportation Science (Dagstuhl Seminar 22192)

Authors: Martin Gairing, Carolina Osorio, Britta Peis, David Watling, and Katharina Eickhoff

Published in: Dagstuhl Reports, Volume 12, Issue 5 (2022)

Abstract
Traffic assignment models are crucial for transport planners to be able to predict the congestion, environmental and social impacts of transport policies, for example in the light of possible changes to the infrastructure, to the transport services offered, or to the prices charged to travellers. The motivation for this series of seminars - of which this seminar was the third - is the prevalence in the transportation community of basing such predictions on complex computer-based simulations that are capable of resolving many elements of a real systems, while on the other hand, the theory of dynamic traffic assignments (in terms of equilibrium existence, computability and efficiency) had not matured to the point matching the model complexity inherent in simulations. Progress has been made on this issue in the first two seminars (Dagstuhl Seminar 15412 and 18102), by bringing together leading scientists in the areas of traffic simulation, algorithmic game theory and dynamic traffic assignment. We continued this process this seminar. Moreover, we started to address the growing real-life challenge of new kinds of 'mobility service' emerging, before the tools are available to incorporate them in such planning models. These services include intelligent/dynamic ride-sharing and car-sharing, through to fully autonomous vehicles, provided potentially by a variety of competing operators.
Cite as

Martin Gairing, Carolina Osorio, Britta Peis, David Watling, and Katharina Eickhoff. Dynamic Traffic Models in Transportation Science (Dagstuhl Seminar 22192). In Dagstuhl Reports, Volume 12, Issue 5, pp. 92-111, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{gairing_et_al:DagRep.12.5.92,
  author =	{Gairing, Martin and Osorio, Carolina and Peis, Britta and Watling, David and Eickhoff, Katharina},
  title =	{{Dynamic Traffic Models in Transportation Science (Dagstuhl Seminar 22192)}},
  pages =	{92--111},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{12},
  number =	{5},
  editor =	{Gairing, Martin and Osorio, Carolina and Peis, Britta and Watling, David and Eickhoff, Katharina},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.5.92},
  URN =		{urn:nbn:de:0030-drops-174441},
  doi =		{10.4230/DagRep.12.5.92},
  annote =	{Keywords: Algorithms and Complexity of traffic equilibrium computations, Dynamic traffic assignment models, Simulation and network optimization}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact