On diameters of transportation and network flow polytopes
Speaker:
Edward Kim, Tu Delft
Date and Time:
Tuesday, September 20, 2011 - 4:30pm to 5:30pm
Abstract:
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.