A maximum flow over time generalizes standard maximum flow by introducing a time component. The object is to send as much flow from source to sink in T time units as possible, where capacities are interpreted as an upper bound on the rate of flow entering an arc. A related problem is the universally maximum flow, which is to send a flow from source to sink that maximizes the amount of flow arriving at the sink by time t simultaneously for all t ≤ T. We consider a further generalization of this problem that allows arc and node capacities to change over time. In particular, given a network with m arcs and n nodes, arc and node capacities that are piecewise constant functions of time with at most k breakpoints and a time bound T, we show how to compute a flow that maximizes the amount of flow reaching the sink in all time intervals (0,t] simultaneously for all 0<t≤T, in O(k2mnlog(kn2/m)) time. The best previous algorithm requires O(nk) maximum-flow computations on a network with (m + n)k arcs and nk nodes. Our algorithm improves on this by a factor of O(nk).
