Duality for balanced submodular flows (Q581206)

A (single source-single sink) flow is called balanced if for all arcs e the flow value x(e) does not exceed a given proportion of the total flow from source to sink. After discussing a basic dual approach which works in the general context of totally ordered sets, the author shows that his approach can be used to solve parametric problems which are equivalent to balanced flow problems. The discussion is further generalized by considering general balanced submodular flow problems. In both cases genuinely polynomial complexity bounds are derived for the resulting algorithms.