Abstract
Flow variation over time is an important feature in network flow problems arising in various applications such as road or air traffic control, production systems, communication networks (e.g., the Internet), and financial flows. The common characteristic are networks with capacities and transit times on the arcs which specify the amount of time it takes for flow to travel through a particular arc. Moreover, in contrast to static flow problems, flow values on arcs may change with time in these networks.
While the ‘maximum s-t-flow over time’ problem can be solved efficiently and ‘min-cost flows over time’ are known to be NP-hard, the complexity of (fractional) ‘multicommodity flows over time’ has been open for many years. We prove that this problem is NP-hard, even for series-parallel networks, and present new and efficient algorithms under certain assumptions on the transit times or on the network topology. As a result, we can draw a complete picture of the complexity landscape for flow over time problems.
Supported by the joint Berlin/Zurich graduate program Combinatorics, Geometry, and Computation (CGC), financed by ETH Zurich and the German Science Foundation (DFG)
Supported in part by the EU Thematic Networks APPOL I & II, Approximation and Online Algorithms, IST-1999-14084, IST-2001-30012.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J. E. Aronson. A survey of dynamic network flows. Annals of Operations Research, 20:1–66, 1989.
R. E. Burkard, K. Dlaska, and B. Klinz. The quickest flow problem. ZOR — Methods and Models of Operations Research, 37:31–58, 1993.
T. Erlebach and K. Jansen. Call scheduling in trees, rings and meshes. In Proceedings of the 30th Hawaii International Conference on System Sciences, pages 221–222. IEEE Computer Society Press, 1997.
L. Fleischer and M. Skutella. The quickest multicommodity flow problem. In W. J. Cook and A. S. Schulz, editors, Integer Programming and Combinatorial Optimization, volume 2337 of Lecture Notes in Computer Science, pages 36–53. Springer, Berlin, 2002.
L. Fleischer and M. Skutella. Minimum cost flows over time without intermediate storage. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 66–75, Baltimore, MD, 2003.
L. K. Fleischer and É Tardos. Efficient continuous-time dynamic network flow algorithms. Operations Research Letters, 23:71–80, 1998.
L. R. Ford and D. R. Fulkerson. Constructing maximal dynamic flows from static flows. Operations Research, 6:419–433, 1958.
L. R. Ford and D. R. Fulkerson. Flows in Networks. Princeton University Press, Princeton, NJ, 1962.
B. Hoppe. Efficient dynamic network flow algorithms. PhD thesis, Cornell University, 1995.
B. Hoppe and É. Tardos. The quickest transshipment problem. Mathematics of Operations Research, 25:36–62, 2000.
B. Klinz and G. J. Woeginger. Minimum cost dynamic flows: The series-parallel case. In E. Balas and J. Clausen, editors, Integer Programming and Combinatorial Optimization, volume 920 of Lecture Notes in Computer Science, pages 329–343. Springer, Berlin, 1995.
N. Megiddo. Combinatorial optimization with rational objective functions. Mathematics of Operations Research, 4:414–424, 1979.
W. B. Powell, P. Jaillet, and A. Odoni. Stochastic and dynamic networks and routing. In M. O. Ball, T. L. Magnanti, C. L. Monma, and G. L. Nemhauser, editors, Network Routing, volume 8 of Handbooks in Operations Research and Management Science, chapter 3, pages 141–295. North-Holland, Amsterdam, The Netherlands, 1995.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hall, A., Hippler, S., Skutella, M. (2003). Multicommodity Flows over Time: Efficient Algorithms and Complexity. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds) Automata, Languages and Programming. ICALP 2003. Lecture Notes in Computer Science, vol 2719. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45061-0_33
Download citation
DOI: https://doi.org/10.1007/3-540-45061-0_33
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40493-4
Online ISBN: 978-3-540-45061-0
eBook Packages: Springer Book Archive