KAIST Discrete Math Seminar

Transportation and network polytopes are classical objects in operations research. In this talk, we focus on recent advances on the diameters of several classes of transportation polytopes, motivated by the efficiency of the simplex algorithm. In particular, we discuss results on 2-way transportation polytopes, including a recent result of Stougie and report on joint work with Bruhn-Fujimoto and Pilaud, concerning 2-way transportation polytopes with a certain support structure. We also present a bound on 3-way transportation polytopes in joint work with De Loera, Onn, and Santos. To conclude, we discuss avenues for future work on transportation polytopes and their diameters.