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.

Weitere Dienste

Verfasserangaben: Stefan Ruzika, Markus Thiemann urn:nbn:de:hbz:386-kluedo-16676 Report in Wirtschaftsmathematik (WIMA Report) (130) Bericht Englisch 2010 2010 Technische Universität Kaiserslautern 19.11.2010 fptas ; multiple objective optimization; polynomial algorithms ; quickest path ; robust network flows Fachbereich Mathematik 5 Naturwissenschaften und Mathematik / 510 Mathematik Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011

$Rev: 13581$