A linear bound on the diameter of the transportation polytope (Q858109)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 5082293
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A linear bound on the diameter of the transportation polytope |
scientific article; zbMATH DE number 5082293 |
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
0.8743122220039368
0 references
0.8670534491539001
0 references
0.8666038513183594
0 references
