A linear bound on the diameter of the transportation polytope
The authors show that for any pair of vertices \(X,Y\) of an \(m \times n\) transportation polytope at most \(8(m+n-2)\) pivot steps are required to go from \(X\) to \(Y\). This improves the quadratic bound \(mn\) on the maximum diameter of a transpotation polytope given in \textit{V. A. Yemelichev, M. M. Kovalev} and \textit{M. K. Kravtsov} [Polytopes, Graphs and Optimization, Cambridge University Press (1984; Zbl 0523.52002)].
scientific article; zbMATH DE number 5082293