We present two different 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. These solutions not only feature a simple structure but can also be computed very efficiently in polynomial time.

Secondly, we investigate ‘condensed’ time-expanded networks which rely on a rougher discretization of time. Unfortunately, there is a natural tradeoff between the roughness of the discretization and the quality of the achievable solutions. However, 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, this approach yields a fully polynomial time approximation scheme for the quickest multicommodity flow problem and also for more general problems.