The monotone diameter of a polytope is the worst case, over linear objectives and starting vertices, of the length of the shortest improving (monotone) edge path to the optimal vertex; it is the pivot-rule-independent geometric quantity that lower-bounds, in the worst case, the iteration count of every simplex pivot rule. For the m×nm\times n transportation polytope — the feasible region of the classical transportation linear program — Blanchard, De Loera, and Louveaux proved that the monotone diameter is at most nn for 2×n2\times n transportation polytopes and at most e⋅k! nke\cdot k!\,n^{k} when the number kk of sources is fixed, and they conjectured (Conjecture 4.2) that the monotone diameter of m×nm\times n transportation polytopes is linear in mm and nn. When both mm and nn grow, no polynomial bound is known: the only general estimates are Kalai's subexponential bound for arbitrary polyhedra. The problem is to prove or disprove the linear bound, i.e. the existence of a universal constant CC with monotone diameter at most C (m+n)C\,(m+n). A proof would give the first sharp, rule-independent guarantee on simplex path lengths for a core operations-research LP family; a refutation would establish the first superlinear lower bound on the worst-case iteration count of every pivot rule on this family, showing that no pivot rule can guarantee a linear number of improving pivots on all transportation LPs.

Background

The simplex method solves a linear program by walking along edges of its feasible polyhedron from a starting vertex to an optimal one, each step decreasing the objective; a pivot rule decides which improving edge to take next. Whether some pivot rule always takes polynomially many steps is a famous open problem of linear optimization. The geometry behind it is captured by monotone paths: given an objective vector cc that is nondegenerate (no two vertices have equal value), orienting every edge of the polytope towards the endpoint with smaller cc-value yields an acyclic directed graph. A cc-monotone path is a directed path in this graph ending at the optimal vertex; the cc-monotone diameter is the maximum, over starting vertices, of the length of a shortest cc-monotone path, and the monotone diameter of the polytope maximizes this over all objectives. Since every simplex run follows a monotone path, the monotone diameter lower-bounds the worst-case iteration count of every pivot rule, and it fits into the chain (undirected) diameter ≤\le monotone diameter ≤\le π\pi-pivot height ≤\le height, where the height is the length of the longest monotone path and the π\pi-pivot height is the worst path produced by a specific rule π\pi (e.g. Bland's, Dantzig's, greatest-improvement, steepest-edge). The transportation polytope P(a,b)P(a,b) is the set of nonnegative m×nm\times n matrices with prescribed row sums a∈R≥0ma\in\mathbb{R}^m_{\ge 0} and column sums b∈R≥0nb\in\mathbb{R}^n_{\ge 0} of equal total; it has dimension (m−1)(n−1)(m-1)(n-1), mnmn facets xij≥0x_{ij}\ge 0, and vertices corresponding, when the margins are nondegenerate, to the spanning trees of the complete bipartite graph Km,nK_{m,n} (its constraint matrix is totally unimodular, i.e. every subdeterminant is 00 or ±1\pm1). For this polytope the Hirsch bound — diameter at most number of facets minus dimension — equals m+n−1m+n-1, and the undirected diameter indeed satisfies it, since Borgwardt, De Loera, and Finhold proved that network-flow polytopes (a class containing transportation polytopes) satisfy the Hirsch conjecture. The directed, monotone version is much harder in general: Todd showed in 1980 that the monotone Hirsch conjecture (monotone diameter at most facets minus dimension) is false for arbitrary polytopes of dimension at least 4, and the best general monotone-diameter bound remains Kalai's 1992 subexponential bound of order m2mm^{2\sqrt{m}} for nn-polytopes with mm facets. For transportation polytopes specifically, Borgwardt, De Loera, Finhold, and Miller proved in their circuit-diameter hierarchy that the m+n−1m+n-1 bound holds in most of their diameter notions, classical Hirsch holds for 3×n3\times n transportation polytopes, and the monotone Hirsch bound holds for 2×n2\times n. Blanchard, De Loera, and Louveaux then studied monotone paths systematically. Their zonotope reduction — a zonotope being a Minkowski sum (pointwise sum) of line segments — shows the monotone diameter of any polytope is at most its number of distinct edge directions; this immediately gives polynomial monotone diameters for matroid and polymatroid polytopes (at most (n2)\binom{n}{2}), but fails for transportation polytopes because their edge directions (supported on cycles of Km,nK_{m,n}) are exponentially many. For transportation polytopes they proved the monotone diameter is at most nn in the 2×n2\times n case and at most e⋅k! nke\cdot k!\,n^{k} for k×nk\times n, which is polynomial in nn only for a fixed number kk of sources, and they posed Conjecture 4.2: the monotone diameter of m×nm\times n transportation polytopes is linear in mm and nn. In the Hirsch-normalized scale of this family, where the facet-minus-dimension bound is m+n−1m+n-1, the conjecture asks for a bound C⋅(m+n)C\cdot(m+n) with a universal constant CC; even the intermediate goal of any bound polynomial in mm and nn with both parameters growing has remained open since 2020.

Problem Statement

Prove or disprove Conjecture 4.2 of Blanchard–De Loera–Louveaux: there exists a universal constant CC such that the monotone diameter of every m×nm\times n transportation polytope P(a,b)={x∈R≥0m×n:∑jxij=ai, ∑ixij=bj}P(a,b)=\{x\in\mathbb{R}^{m\times n}_{\ge 0}:\sum_j x_{ij}=a_i,\ \sum_i x_{ij}=b_j\} (with nonnegative margins of equal total) is at most C (m+n)C\,(m+n), for all m,n≥2m,n\ge 2. In terms of paths, this requires that for every such polytope, every cost vector cc that is nondegenerate on it (no two vertices of P(a,b)P(a,b) with equal cc-value), and every vertex vv of P(a,b)P(a,b), there exists a cc-monotone path — a path of edges each strictly decreasing the cc-value — from vv to the cc-optimal vertex, of length at most C (m+n)C\,(m+n); the bound must also cover degenerate cost vectors, so a proof may not silently restrict to nondegenerate objectives. The bound must be pivot-rule-independent, since the monotone diameter minimizes over all improving paths. The sharpest current bound is e⋅k! nke\cdot k!\,n^{k}, polynomial only for fixed kk, and without it only Kalai's subexponential bound for general polyhedra applies. A disproof must exhibit an infinite family of transportation polytopes, with dimensions tending to infinity, in which the shortest monotone path from some vertex to the optimum is superlinear in m+nm+n (i.e., exceeds C (m+n)C\,(m+n) for every constant CC along the family); a single finite instance does not suffice.

References

  1. Moïse Blanchard, Jesús A. De Loera, Quentin Louveaux, "On the Length of Monotone Paths in Polyhedra", SIAM Journal on Discrete Mathematics 35(3):1746–1768, 2021. DOI 10.1137/20M1315646; arXiv:2001.09575. https://doi.org/10.1137/20M1315646 (source of the open question)
  2. Steffen Borgwardt, Jesús A. De Loera, Elisabeth Finhold, Jacob Miller, "The hierarchy of circuit diameters and transportation polytopes", Discrete Applied Mathematics 240:8–24, 2018. DOI 10.1016/j.dam.2015.10.017; arXiv:1411.1701. https://doi.org/10.1016/j.dam.2015.10.017
  3. Steffen Borgwardt, Jesús A. De Loera, Elisabeth Finhold, "The diameters of network-flow polytopes satisfy the Hirsch conjecture", Mathematical Programming 171(1–2):283–309, 2018. DOI 10.1007/s10107-017-1176-x. https://doi.org/10.1007/s10107-017-1176-x
  4. Michael J. Todd, "The Monotonic Bounded Hirsch Conjecture is False for Dimension at Least 4", Mathematics of Operations Research 5(4):599–601, 1980. DOI 10.1287/moor.5.4.599. https://doi.org/10.1287/moor.5.4.599
  5. Gil Kalai, "Upper bounds for the diameter and height of graphs of convex polyhedra", Discrete & Computational Geometry 8(4):363–372, 1992. DOI 10.1007/BF02293053. https://doi.org/10.1007/BF02293053
  6. Alexander E. Black, Jesús A. De Loera, Sean Kafer, Laura Sanità, "On the Simplex Method for 0/1-Polytopes", Mathematics of Operations Research 50(2):1398–1420, 2025. DOI 10.1287/moor.2021.0345; arXiv:2111.14050. https://doi.org/10.1287/moor.2021.0345
  7. Yasuko Matsui, Noriyoshi Sukegawa, Ping Zhan, "Monotone Diameter of Bisubmodular Polyhedra", Operations Research Forum 4(4):76, 2023. DOI 10.1007/s43069-023-00260-1. https://doi.org/10.1007/s43069-023-00260-1
  8. Christian Nöbel, Raphael Steiner, "Complexity of polytope diameters via perfect matchings", Mathematical Programming, 2026 (published online 2026-02-19; SODA 2025 version: Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, DOI 10.1137/1.9781611978322.74). DOI 10.1007/s10107-026-02324-6; arXiv:2404.04158. https://doi.org/10.1007/s10107-026-02324-6
  9. Alexander E. Black, Raphael Steiner, "Finding Short Paths on Simple Polytopes", arXiv:2603.05482, 2026. https://arxiv.org/abs/2603.05482
  10. Alexander E. Black, Lei Xue, "Any Proof of Polynomial Hirsch Must be Completely Incoherent", arXiv:2607.11628, 2026. https://arxiv.org/abs/2607.11628