Report Number: CS-TR-91-1374
Institution: Stanford University, Department of Computer Science
Title: Polynomial dual network simplex algorithms
Author: Orlin, James B.
Author: Plotkin, Serge A.
Author: Tardos, Eva
Date: August 1991
Abstract: We 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(m2 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 nB, m log
n))-time implementation of a strategy that requires somewhat