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.

Download full text files

Export metadata

Additional Services

Search Google Scholar
Metadaten
Author:Stefan Ruzika, Markus Thiemann
URN:urn:nbn:de:hbz:386-kluedo-16676
Series (Serial Number):Report in Wirtschaftsmathematik (WIMA Report) (130)
Document Type:Report
Language of publication:English
Year of Completion:2010
Year of first Publication:2010
Publishing Institution:Technische Universität Kaiserslautern
Date of the Publication (Server):2010/11/19
Tag:fptas; multiple objective optimization; polynomial algorithms; quickest path; robust network flows
Faculties / Organisational entities:Kaiserslautern - Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
Licence (German):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011