Parametric maximal flows in generalized networks – complexity and algorithms

Abstract

The problem of determining parametric maximal flows in networks with gains is considered. A worst-case analysis with respect to the number of breakpoints in the optimal objective value function is performed for both parametric flows leaving the source and parametric capacities of the arcs. The result is an exponential growth of the number of breakpoints depending on the number of vertices in the underlying graph. From there, the idea of a horizontal approximation algorithm developed from Hamachee and Foulds [5] is extended to generalized flows. In each iteration the horizontal approach makes an improvement which is a piecewise linear function of the whole parameter interval. This process can be applied up to optimality