Page Content
to Navigation
Publications
| 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 |
Talks
| 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? | |
| Lehrstuhl-2-Seminar 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 | |
| Berlin-Poznań-Seminar 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 |