direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content


Approximating Earliest Arrival Flows in Arbitrary Networks
Citation key GrossKappmeierSchmidt+2012
Author Groß, Martin and Kappmeier, Jan-Philipp W. and Schmidt, Melanie and Schmidt, Daniel
Title of Book Algorithms – ESA 2012
Pages 551-562
Year 2012
ISBN 978-3-642-33089-6
DOI 10.1007/978-3-642-33090-2_48
Volume 7501
Editor Epstein, Leah and Ferragina, Paolo
Publisher Springer Berlin / Heidelberg
Series Lecture Notes in Computer Science
Institution TU Berlin, Germany
Abstract The earliest arrival flow problem is motivated by evacuation planning. It asks for a flow over time in a network with supplies and demands that maximizes the satisfied demands at every point in time. Gale [1959] has shown the existence of such flows for networks with a single source and sink. For multiple sources and a single sink the existence follows from work by Minieka [1973] and an exact algorithm has been presented by Baumann and Skutella [FOCS ’06]. If multiple sinks are present, it is known that earliest arrival flows do not exist in general. We address the open question of approximating earliest arrival flows in arbitrary networks with multiple sinks and present constructive approximations of time and value for them. We give tight bounds for the best possible approximation factor in most cases. In particular, we show that there is always a 2-value-approximation of earliest arrival flows and that no better approximation factor is possible in general. Furthermore, we describe an FPTAS for computing the best possible approximation factor (which might be better than 2) along with the corresponding flow for any given instance.
Bibtex Type of Publication in collection
Link to original publication Download Bibtex entry


Preprint 018-2009
Dressler, Daniel and Groß, Martin and Kappmeier, Jan-Philipp and Kelter, Timon and Kulbatzki, Joscha and Plümpe, Daniel and Schlechter, Gordon and Schmidt, Melanie and Skutella, Martin and Temme, Sylvie.
On the Use of Network Flow Techniques for Assigning Evacuees to Exits.

Preprint 001-2012
Kappmeier, Jan-Philipp W. and Matuschke, Jannik and Peis, Britta.
Abstract flows over time: A first step towards solving dynamic packing problems.


Delegation Visit of the Beijing University of Technology
Technische Universität Berlin, Germany, 31.10.2013
Evacuation Optimization (download)
COGA Doktoranden- & Diplomanden-Seminar
Technische Universität Berlin, Germany, 21.02.2013
How to TikZ?
Technische Universität Dortmund, Germany, 29.01.2013
Generalizations of Flows over Time and a Fake Application 

International Symposium on Algorithms and Computation
National Taiwan University, 台北市 Taipei, 20.12.2012
Abstract Flows over Time: A First Step towards Solving Dynamic Packing Problems
Freie Universität Berlin, Germany, 10.11.2012
Abstract Flows over Time
International Symposium on Mathematical Programming
Technische Universität Berlin, Germany, 23.08.2012
Flows over Time with Negative Transit Times and Arc Release Dates

International Conference on Evacuation Modeling and Management
Northwestern University, Evanston, USA, 15.08.2012
Evacuation of a 22-Story Building in Simulation and Reality
Cologne Twente Workshop on Graphs and combinatorial Optimization
Universität der Bundeswehr, Munich, Germany, 30.05.2012
Talk on Network Flows over Time with Negative Transit Times and Arc Release Dates.
Tools Seminar
Technische Universität Berlin, Germany, 09.02.2012
How to TikZ?

COGA Doktoranden- & Diplomanden-Seminar
Technische Universität Berlin, Germany, 07.12.2010
How to TikZ? (updated version of 13.12.2010)

International Conference on Evacuation Management 2009
Scheveningen, Netherlands, 24.09.2009
On the Use Network Flow Techniques for Assigning Evacuees to Exits

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

This site uses Matomo for anonymized webanalysis. Visit Data Privacy for more information and opt-out options.