Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Transportation polytopes: a twenty-year update

Algebra & Discrete Mathematics

Speaker: Jesus De Loera, UC Davis
Location: 693 Kerr
Start time: 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.