Conditions for the existence of solutions of the three-dimensional planar transportation problem (Q1081532): Difference between revisions

For an \(m\times n\times p\) matrix \(X=(x_{ijk})\) let \(x_{.jk}\), \(x_{i.k}\) and \(x_{ij.}\) be the partial sums obtained by summation over the subscript replaced by a dot. The three planar sums transportation polytope is defined as follows: \(T(A,B,C)=\{X\geq 0|\) \(x_{.jk}=a_{jk}\), \(x_{i.k}=b_{ik}\), \(x_{ij.}=c_{ij}\) for all i, j and \(k\}\) where \(A=(a_{jk})\), \(B=(b_{ik})\) and \(C=(c_{ij})\) are given matrices of appropriate size. Necessary conditions on A, B and C for T(A,B,C) to be nonempty were given by E. D. Schell, K. B. Haley, J. Morávek, the author and G. Smith. The author provides a comprehensive survey of these results and presents some unsolved problems concerning T(A,B,C). A most important open question is e.g. if there is a genuinely polynomial algorithm to decide whether T(A,B,C) is nonempty.