Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Transportation problems are classical problems whose polytopes lie at the core of operations research. While their combinatorial diameter has long been studied, it is still open if their combinatorial diameters are bounded above by the Hirsch bound in general. In this talk I will review a recently introduced hierarchy of circuit diameters that generalize the notion combinatorial diameter, and will discuss these diameters as they pertain to transportation polytopes. In particular it can be shown, for all but small values of m and n, there exists mxn transportation polytopes who have a lower bound of the Hirsch bound for all these notions of circuit diameters. For the strong circuit diameter we show that 3xn transportation polytopes are at most the Hirsch bound and 2xn transportation polytopes are usually 2 less than the Hirsch bound. For the combinatorial diameter we show that 2xn transportation polytopes are usually 1 less than the Hirsch bound (an improvement by 1 on previous result), that this same bound holds for the monotone combinatorial diameter, and that 3xn transportation are also at most the Hirsch bound. This is joint work with S. Borgwardt, J. A. De Loera, and E. Finhold