Traditionally, flows over time are solved in time expanded networks
which contain one copy of the original network for each discrete
time step. While this method makes available the whole algorithmic
toolbox developed for static flows, its main and often fatal
drawback is the enormous size of the time expanded network. In
particular, this approach usually does not lead to efficient
algorithms with running time polynomial in the input size since the
size of the time expanded network is only pseudo-polynomial.
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 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.
