Jesus de Loera (UC Davis): Transportation polytopes: a twenty-year update

A transportation polytope consists of all multidimensional arrays of nonnegative numbers that satisfy certain sum conditions on subsets of the entries. They are among the first ever studied combinatorial optimization problems, going back to the 1930's work of Kantorovich and Koopmans. Transportation polytopes 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 report on the following ``universality theorem'': Every rational convex polytope is strongly isomorphic to a 3-way, 2-margin transportation polytope. This has very interesting consequences for integer programming and statistics. It is indeed useful to the solution of several open questions collected in the 1984 monograph by Yemelichev-Kovalev-Kravtsov and the 1986 survey paper of Vlach. For young people I will try to state several open questions, even for the classical 2-way case.

Based on joint papers with Ed Kim, Fu Liu, Francisco Santos and Shmuel Onn.