Min-Max Quickest Path Problems

  • In a dynamic network, the quickest path problem asks for a path such that a given amount of flow can be sent from source to sink via this path in minimal time. In practical settings, for example in evacuation or transportation planning, the problem parameters might not be known exactly a-priori. It is therefore of interest to consider robust versions of these problems in which travel times and/or capacities of arcs depend on a certain scenario. In this article, min-max versions of robust quickest path problems are investigated and, depending on their complexity status, exact algorithms or fully polynomial-time approximation schemes are proposed.

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Stefan Ruzika, Markus Thiemann
URN (permanent link):urn:nbn:de:hbz:386-kluedo-16676
Serie (Series number):Report in Wirtschaftsmathematik (WIMA Report) (130)
Document Type:Report
Language of publication:English
Year of Completion:2010
Year of Publication:2010
Publishing Institute:Technische Universität Kaiserslautern
Tag:fptas ; multiple objective optimization; polynomial algorithms ; quickest path ; robust network flows
Faculties / Organisational entities:Fachbereich Mathematik
DDC-Cassification:510 Mathematik

$Rev: 12793 $