Asymptotically Optimal Solution for Transportation Problem with Almost Arbitrary Capacities

Consider a following transportation problem: given a set of nodes, some pairs of them are connected; each node has some initial quantity of a single-type product and a demand of the same product; the amount of product that can be transferred between connected nodes per time unit is limited; assuming that summary demand equals summary initial quantity of the product, what is the minimal time required to satisfy all the demands? For the case of constant capacities over time for each pair of connected channels, this problem is quite a simple optimization problem (linear programming or simpler) but might become very hard if it is not constant. In this paper we present a proof that for the problem with “averagable” in some sense capacity functions one can construct a suboptimal solution based on the solution of the “averaged” problem that happens to be asymptotically optimal.