- Treffer 1 von 1
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.
Verfasser*innenangaben: | Stefan Ruzika, Markus Thiemann |
---|---|
URN: | urn:nbn:de:hbz:386-kluedo-16676 |
Schriftenreihe (Bandnummer): | Report in Wirtschaftsmathematik (WIMA Report) (130) |
Dokumentart: | Bericht |
Sprache der Veröffentlichung: | Englisch |
Jahr der Fertigstellung: | 2010 |
Jahr der Erstveröffentlichung: | 2010 |
Veröffentlichende Institution: | Technische Universität Kaiserslautern |
Datum der Publikation (Server): | 19.11.2010 |
Freies Schlagwort / Tag: | fptas; multiple objective optimization; polynomial algorithms; quickest path; robust network flows |
Fachbereiche / Organisatorische Einheiten: | Kaiserslautern - Fachbereich Mathematik |
DDC-Sachgruppen: | 5 Naturwissenschaften und Mathematik / 510 Mathematik |
Lizenz (Deutsch): | Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011 |