A polynomial dual simplex algorithm for the generalized circulation problem
A polynomial dual simplex algorithm for the generalized circulation problem
复制标题
广义循环问题的多项式对偶单纯形算法
作者：
D. Goldfarb;Zhiying Jin;Yiqing Lin
摘要。本文为广义循环问题提供了多项式双重单纯形算法。给出了该算法的有效实现，该算法的运行时间为O（m2（m+nlogn）logB），其中n是节点的数量，m是弧的数量，b是用于使用的最大整数，用于代表网络中的理性收益因素和积分能力。该运行时间与迄今为止用于解决广义循环问题的任何组合算法的运行时间一样快。
Abstract.This paper presents a polynomial-time dual simplex algorithm for the generalized circulation problem. An efficient implementation of this algorithm is given that has a worst-case running time of O(m2(m+nlogn)logB), where n is the number of nodes, m is the number of arcs and B is the largest integer used to represent the rational gain factors and integral capacities in the network. This running time is as fast as the running time of any combinatorial algorithm that has been proposed thus far for solving the generalized circulation problem.