A Polynomially Bounded Algorithm for a Nonlinear Network Allocation Problem

This paper presents an algorithm for determining the optimal allocation to demand points when the distribution system is a capacitated arborescence of N arcs and the cost (return) functions are convex (concave). It is proved that the algorithm generates an optimal solution by solving at most N(N + 1)/2 single-constraint subproblems. If the cost functions allow the Lagrange multiplier for the subproblems to be evaluated in polynomial time, then this is a polynomial algorithm. The analysis is motivated by the problem of allocating spare capacity in the loop plant portion of telephone networks.