Polynomial Dual Network Simplex Algorithms
James B. Orlin, Serge A. Plotkin, Éva Tardos · 1991
1j. AGSTRACT (AMo&sflum JO0 w6mWWe show how to use polynomial and strongly polynomial capacity scaling algorithms for the transshipment problem to design a polynomial dual network simplex pivot rule.Our best pivoting strategy leads to an O(M 2 log n) bound on the number of pivots, where n and m denotes the number of nodes and arcs in the input network.If the demands are integral and at most B, we also give an O(m(m + n log n) min(log riB, in logn))-time implementation of a strategy that requires somewhat more pivots. 6UBJECT TIRMS IS.