On some properties of three-index transportation polytopes

M. A. Kravtsov ; A. P. Krachkovskii

Diskretnaya Matematika, Tome 11 (1999) no. 3, pp. 109-125

Résumé

For any three-index planar transportation polytope (3-PTP) $M$ of order $m\times n\times k$ and dimensionality $d$, we give a three-index axial transportation polytope (3-ATP) $M'$ of order $mk\times nk\times mn$, with a $d$-face which is combinatorially equivalent to the polytope $M$, and vice versa, for any 3-ATP $M$ of order $m\times n\times k$ we give a 3-PTP $M'$ of order $(m+1)\times (n+1)\times (k+1)$, with an $(mnk-m-n-k+2)$-face which is combinatorially equivalent to the polytope $M$. With the use of these results, we present a series of new properties of three-index transportation polytopes. The research was supported by the Foundation for Basic Research of Republic Byelarus, grant $\Phi$95-70.