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. Solving these problems raises issues that do not
arise in standard network flows. One issue is the question of
storage of flow at intermediate nodes. In most applications (such
as, e.g., traffic routing, evacuation planning, telecommunications
etc.), intermediate storage is limited, undesired, or prohibited.
The minimum cost flow over time problem is NP-hard. In this paper
we 1) prove that the minimum cost flow over time never requires
storage; 2) provide the first approximation scheme for minimum cost
flows over time that does not require storage; 3) provide the first
approximation scheme for minimum cost flows over time that meets
hard cost constraints, while approximating only makespan.
Our approach is based on a condensed variant of time-expanded
networks. It also yields fast approximation schemes with simple
solutions for the quickest multicommodity flow problem.
Finally, using completely different techniques, we describe a very
simple capacity scaling FPAS for the minimum cost flow over time
problem when costs are proportional to transit times. The algorithm
builds upon our observation about the structure of optimal solutions
to this problem: they are universally quickest flows. Again, the
FPAS does not use intermediate node storage. In contrast to the
preceding algorithms that use a time-expanded network, this FPAS
runs directly on the original network.
