Approximating Earliest Arrival Flows in Arbitrary Networks
Groß, Martin and Kappmeier, JanPhilipp W. and Schmidt, Daniel R. and Schmidt, Melanie
(2012)
Approximating Earliest Arrival Flows in Arbitrary Networks.
Published In:
Algorithms – ESA 2012, Lecture Notes in Computer Science. 7501 Springer 2012, pp. 551562.
Abstract
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 approx imations 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 2valueapproximation 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.
Export as:  [error in script] 

Editorial actions:  View Item (Login required) 
Item Type:  Proceedings article 

Citations:  [error in script] [error in script] 
Subjects: 

Subjects:  68XX Computer science > 68Qxx Theory of computing > 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) 68XX Computer science > 68Qxx Theory of computing > 68Q25 Analysis of algorithms and problem complexity 68XX Computer science > 68Rxx Discrete mathematics in relation to computer science > 68R05 Combinatorics 
Divisions:  Institute of Computer Science 
Depositing User:  Daniel R. Schmidt 
Date Deposited:  03 Apr 2014 11:09 
Last Modified:  03 Apr 2014 11:09 
ZAIK Number:  [error in script] 

Depositing User:  Daniel R. Schmidt 
Date Deposited:  03 Apr 2014 11:09 
Last Modified:  03 Apr 2014 11:09 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/773 