Quickest Flows Over Time

Flows over time (also called dynamic flows) generalize standard network flows by introducing an element of time. They naturally model problems where travel and transmission are not instantaneous. Traditionally, flows over time are solved
in time-expanded networks that contain one copy of the original network for each discrete time step. While this method makes available the whole algorithmic tool-box developed for static flows, its main and often fatal drawback is the enormous size of the time-expanded network. We present several approaches for coping with this difficulty. Firstly, inspired by the work of Ford and Fulkerson on maximal s-t-flows over time (or ‘maximal dynamic s-t-flows’), we show that static, length-bounded flows lead to provably good multicommodity flows over time. Secondly, we investigate ‘condensed’ time-expanded networks which rely on a rougher discretization of time. We prove that a solution of arbitrary precision can be computed in polynomial time through an appropriate discretization leading to a condensed time-expanded network of polynomial size. In particular, our approach yields fully polynomial time approximation schemes for the NP-hard quickest min-cost and multi-commodity flow problems. For single commodity problems, we show that storage of flow at intermediate nodes is unnecessary; and our approximation schemes do not use any.

By: Lisa K. Fleischer, Martin Skutella

Published in: RC22833 in 2003


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to reports@us.ibm.com .