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. Another crucial phenomenon in many
of those applications is that the time taken to traverse an edge
varies with the current amount of flow on this edge. Since it is
already a highly nontrivial problem to map these two aspects into an
appropriate and tractable mathematical network flow model, there are
hardly any algorithmic techniques known which are capable of
providing reasonable solutions even for networks of rather modest
size.
Our work is inspired by the groundbreaking result of Ford and
Fulkerson on "dynamic" s-t-flows in networks with fixed transit
times on the edges and a fixed time horizon. They showed that there
always exists a maximal flow over time which sends flow on certain
s-t-paths at a constant rate as long as there is enough time
left for the flow along a path to arrive at the sink.
Although this result does not hold for the more general setting with
load-dependent transit times on the edges, we can prove that there
always exists a provably good solution of this structure. Moreover,
such a solution can be determined very efficiently by only one
minimum convex cost flow computation on the underlying "static"
network. Finally, we show that the time-dependent flow problem
under consideration is NP-hard and even cannot be approximated with
arbitrary precision in polynomial time, unless P=NP.
