Conditions for the existence of solutions of the three-dimensional planar transportation problem
type: Item
instance of: scholarly article
title: Conditions for the existence of solutions of the three-dimensional planar transportation problem
zbMATH Open document ID: 0601.90105
DOI: 10.1016/0166-218X(86)90069-7
published in: Discrete Applied Mathematics
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C08
zbMATH DE Number: 3970522
zbMATH Keywords: open problems
zbMATH Keywords: three planar sums transportation polytope
zbMATH Keywords: survey
author: Milan Vlach
reviewed by: László Mihályffy
MaRDI profile type: Publication
cites work: Q3673577
cites work: A theorem on flows in networks
cites work: The Multi-Index Problem
cites work: Zurückführung des Stundenplanproblems auf ein dreidimensionales Transportproblem
cites work: Is binary encoding appropriate for the problem-language relationship?
cites work: Letter to the Editor—On the Necessary Conditions for the Existence of the Solution of the Multi-Index Transportation Problem
cites work: On necessary conditions for a class of systems of linear inequalities
cites work: Q3948879
cites work: Zurückführung eines sortenproblems auf das dreidimensionale transportproblem
cites work: Technical Note—Further Necessary Conditions for the Existence of a Solution to the Multi-Index Problem
cites work: Q4086961
cites work: Some Comments On A Note About Timetabling*
full work available at URL: 0166-218x(86)90069-7
OpenAlex ID: W2025533513
description: scientific article; zbMATH DE number 3970522