Transportation polytopes: a twenty-year updateAlgebra & Discrete Mathematics
|Jesus De Loera, UC Davis
|Fri, Oct 7 2005, 1:10PM
A transportation polytope consists of all multidimensional arrays of nonnegative numbers that satisfy certain sum conditions on subsets of the entries. They arise naturally in optimization and statistics and have also interest for pure mathematics since permutation matrices, latin squares, magic squares, appear as lattice points or vertices of these polytopes.
In this talk I will survey recent advances on the understanding of the combinatorics and geometry of these polyhedra. In particular, I will give a complete report on the status of a list of open questions collected in the 1984 monograph by Yemelichev-Kovalev-Kravtsov and the 1986 survey paper of Vlach.