A polynomial algorithm for minimum quadratic cost flow problems

Network flow problems with quadratic separable costs appear in a number of important applications such as; approximating input-output matrices in economy; projecting and forecasting traffic matrices in telecommunication networks; solving nondifferentiable cost flow problems by subgradient algorithms. It is shown that the scaling technique introduced by Edmonds and Karp (1972) in the case of linear cost flows for deriving a polynomial complexity bound for the out-of-kilter method, may be extended to quadratic cost flows and leads to a polynomial algorithm for this class of problems. The method may be applied to the solution of singly constrained quadratic programs and thus provides an alternative approach to the polynomial algorithm suggested by Helgason, Kennington and Lall (1980).