Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

A linear bound on the diameter of the transportation polytope

Student-Run Research Seminar

Speaker: Eddie Kim, UC Davis
Location: 2112 MSB
Start time: Wed, Feb 21 2007, 12:10PM

Transportation polytopes are well-known objects in operations research, statistics, and mathematical programming. Computation of an initial vertex for feasible transportation polytopes is very fast. Moreover, a generalization of these satisfies a universality property making them of extreme interest in discrete geometric programming. Bounding the diameter of polytopes is of high interest because their diameters are a lower bound to the computation complexity of the simplex method of linear programming. The Hirsch Conjecture attempts to capture the disparate gap between the speed of linear programming in practice and the theoretical worst-case bounds.

In the case of the $m \times n$ transportation polytope, the Hirsch Conjecture implies that the diameter is no more than $m+n-1$. In this talk, we will examine a proof of Brightwell, Stougie, and van den Heuvel: The diameter of the transportation polytope is bounded above by $8(m+n-2)$. Time permitting, we'll consider some similar results in generalized transportation polytopes.