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 more pivots.

http://i.stanford.edu/pub/cstr/reports/cs/tr/91/1374/CS-TR-91-1374.pdf