A polynomial algorithm for minimum quadratic cost flow problems
A polynomial algorithm for minimum quadratic cost flow problems
复制标题
最小二次成本流问题的多项式算法
DOI：
10.1016/0377-2217(84)90160-7
复制
发表时间：
1984
影响因子：
6.4
通讯作者：
M. Minoux
中科院分区：
文献类型：
--
作者：
M. Minoux
具有二次可分离费用的网络流问题在许多重要的应用中出现，例如：近似经济中的输入输出矩阵;电信网络中的业务量矩阵的投影和预测;用次梯度算法求解不可微费用流问题。本文证明了Edmonds和Karp（1972）在线性费用流情况下引入的用于导出出平衡法的多项式复杂性界的尺度技术，可以推广到二次费用流，并导出这类问题的多项式算法。该方法可应用于单约束二次规划的求解，从而为Helgason，肯宁顿和Lall（1980）提出的多项式算法提供了一种替代方法。
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).