The hierarchy of circuit diameters and transportation polytopes

This paper has three contributions: First, we compare the hierarchy of diameters for the m×n-transportation polytopes. We show that the Hirsch conjecture bound of m+n−1 is actually valid in most of these diameter notions. Second, we prove that for 3×n-transportation polytopes the Hirsch conjecture holds in the classical graph diameter. Third, we show for 2×n-transportation polytopes that the stronger monotone Hirsch conjecture holds and improve earlier bounds on the graph diameter.