A Polynomially Bounded Algorithm for a Nonlinear Network Allocation Problem
提出一种算法，用于在容量受限的树状网络中分配资源，最多求解N(N+1)/2个单约束子问题即可得到最优解，适用于成本函数为凸或凹的情形。
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.