Awi Federgruen

Polymatroidal flow network models with multiple sinks

Coauthor(s): Henri Groenevelt.

Abstract:
We consider the polymatroidal flow network model which incorporates two important extensions of the standard maximal flow problem: general concave objective functions of the vector of supplies to a collection of sinks, as well as polymatroidal capacity restrictions on sets of arcs emanating from or pointing to a common node. A number of important applications are reviewed. We show that in this general model the set of feasible supply vectors is itself a polymatroid, and that an optimal solution may be determined by at most 2|V*| – 1 maximum flow computations and optimizations of the objective over a single budget constraint, where |V*| is the number of sinks. Also, it is shown that for the most common types of polymatroidal structures an equivalent flow network can be constructed on an expanded graph but with capacity restrictions on individual arcs only. This transformation allows for the use of classical maximum flow procedures resulting in an often dramatic reduction in complexity.

Source: Networks
Exact Citation:
Federgruen, Awi, and Henri Groenevelt. "Polymatroidal flow network models with multiple sinks." Networks 18, no. 4 (1988): 285-302.
Volume: 18
Number: 4
Pages: 285-302
Date: 1988