A linear bound on the diameter of the transportation polytope (Q858109)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A linear bound on the diameter of the transportation polytope |
scientific article |
Statements
A linear bound on the diameter of the transportation polytope (English)
0 references
8 January 2007
0 references
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)].
0 references
transportation polytope
0 references
diameter
0 references