Solving integer minimum cost flows with separable convex cost objective polynomially
Solving integer minimum cost flows with separable convex cost objective polynomially
复制标题
求解具有可分离凸成本目标多项式的整数最小成本流
DOI：
10.1007/bfb0121104
复制
发表时间：
1986
期刊：
影响因子：
--
通讯作者：
M. Minoux
中科院分区：
文献类型：
--
作者：
M. Minoux
描述了一种多项式算法，用于求解具有弧上可分离凸代价函数和流的完整性限制的最小代价网络流问题。该证明推广了Edmonds和Karp用于证明普通（线性代价）网络流非平衡方法的多项式性的标度方法。
A polynomial algorithm is described to solve minimum cost network flow problems with separable convex cost functions on the arcs and integrality restrictions on the flows. The proof generalizes the scaling approach used by Edmonds and Karp for proving polynomiality of the out-of-kilter method for ordinary (linear cost) network flows.