Abstract of CORC technical report TR-98-02:
Optional Rounding of Fractional Dynamic Flows when Transit Times are
Zero
Lisa Fleischer and J.B. Olin, 1998
A transshipment problem with demands that exceed network capacity can
be solved by sending flow in several waves. How can this be done in
the minimum number, T, of waves, and at minimum cost, if
costs are piece-wise linear convex functions of the flow? In this
paper, we show that this problem can be solved using at most
log T maximum flow computations and one minimum (convex)
cost flow computation. When there is only one sink, this problem can
be solved in the same asymptotic time as one minimum (convex) cost
flow computation. This improves upon the recent algorithm in [5]
which solves the quickest transshipment problem (the above mentioned
problem without costs) on k terminals using
k log T maximum flow computations and
k minimum cost flow computations. Our solutions start with a
stationary fractional flow, as described in [5], and use rounding to
transform this into an integral flow. The rounding procedure takes
O(n) time.
The above problems assume that flow is instantaneous but limited by
bounds on per unit time capacities. The related problem with linear
costs and non-zero transit times is NP-hard. The problem with general
transit times but no costs can be solved in polynomial time, but the
only known polynomial time algorithm to do this repeatedly minimizes
submodular functions using the ellipsoid method [12].