Search Results

Documents authored by Troost, Niklas

Multistage Shortest Path: Instances and Practical Evaluation

Authors: Markus Chimani and Niklas Troost

Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)

A multistage graph problem is a generalization of a traditional graph problem where, instead of a single input graph, we consider a sequence of graphs. We ask for a sequence of solutions, one for each input graph, such that consecutive solutions are as similar as possible. There are several theoretical results on different multistage problems and their complexities, as well as FPT and approximation algorithms. However, there is a severe lack of experimental validation and resulting feedback. Not only are there no algorithmic experiments in literature, we do not even know of any strong set of multistage benchmark instances. In this paper we want to improve on this situation. We consider the natural problem of multistage shortest path (MSP). First, we propose a rich benchmark set, ranging from synthetic to real-world data, and discuss relevant aspects to ensure non-trivial instances, which is a surprisingly delicate task. Secondly, we present an explorative study on heuristic, approximate, and exact algorithms for the MSP problem from a practical point of view. Our practical findings also inform theoretical research in arguing sensible further directions. For example, based on our study we propose to focus on algorithms for multistage instances that do not rely on 2-stage oracles.

Cite as

Markus Chimani and Niklas Troost. Multistage Shortest Path: Instances and Practical Evaluation. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

  author =	{Chimani, Markus and Troost, Niklas},
  title =	{{Multistage Shortest Path: Instances and Practical Evaluation}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{14:1--14:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-275-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{257},
  editor =	{Doty, David and Spirakis, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-179507},
  doi =		{10.4230/LIPIcs.SAND.2023.14},
  annote =	{Keywords: Multistage Graphs, Shortest Paths, Experiments}
Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail