Polynomial Dual Network Simplex Algorithms
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 0(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 0(m(m + n log n) min(log nB, m log n))-time implementation of a strategy that requires somewhat more pivots.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1991
- Accession Number
- ADA254340
Entities
People
- James B. Orlin
- Serge A. Plotkin
- Éva Tardos
Organizations
- Stanford University