Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Transportation polytopes are well-known objects in operations research, mathematical programming and statistics. Classical transportation polytopes are polytopes with variable values recorded in an $m \times n$ table satisfying row-sum and column-sum conditions. A $3$-way transportation polytope is the natural generalization of the classical (or $2$-way) transportation polytope. These are the polyhedra whose points are $l \times m \times n$ tables satisfying certain sum conditions. Bounding the diameter of graphs of polytopes has received a lot of attention because of its connection to the performance of the simplex method for linear programming and, most especially, to try to understand the Hirsch conjecture. In this talk, we discuss the first-known proof giving a quadratic bound on the diameter of axial $3$-way transportation polytopes. Specifically, the graph of the $l \times m \times n$ axial transportation polytope has diameter at most $4(l+m+n-2)^2$. The combinatorics used in the talk is elementary, and will be entirely self-contained. Only some linear algebra will be assumed.