Polynomial Dual Network Simplex Algorithms
STANFORD UNIV CA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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 0m2 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 0mm n log n minlog nB, m log n-time implementation of a strategy that requires somewhat more pivots.
- Operations Research