Optimization of objective functions in polymatroidal network flows

Polymatroidal network flows generalize both network flow theory and matroid optimization. This paper sets and solves a polymatroidal network flow problem with two different objective functions: the first consists in minimizing a linear cost, the second consists in a ‘bottleneck’ objective. It gives two algorithms for the former and an algorithm for the latter. As by-product of the third algorithm the paper obtains a new min-max relation on polymatroidal network flows.