License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SAND.2023.14
URN: urn:nbn:de:0030-drops-179507
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17950/
Go to the corresponding LIPIcs Volume Portal

Chimani, Markus ; Troost, Niklas

Multistage Shortest Path: Instances and Practical Evaluation

pdf-format:
LIPIcs-SAND-2023-14.pdf (2 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{chimani_et_al:LIPIcs.SAND.2023.14,
  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 =		{https://drops.dagstuhl.de/opus/volltexte/2023/17950},
  URN =		{urn:nbn:de:0030-drops-179507},
  doi =		{10.4230/LIPIcs.SAND.2023.14},
  annote =	{Keywords: Multistage Graphs, Shortest Paths, Experiments}
}

Keywords: Multistage Graphs, Shortest Paths, Experiments
Collection: 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)
Issue Date: 2023
Date of publication: 12.06.2023
Supplementary Material: Dataset (Benchmark Instances): https://tcs.uos.de/research/msp

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI