← All problems

Hirsch-sharpness conjecture for 3-way transportation polytopes

16 years old · traced to

Let PP be a non-degenerate 33-way transportation polytope of size p×q×sp \times q \times s, with p,q,s≥3p,q,s \geq 3, defined by 11-marginals. Let G(P)G(P) be its graph, let d=pqs−p−q−s+2d=pqs-p-q-s+2 be its dimension, and let n≤pqsn \leq pqs be the number of facets of PP.

Hirsch-sharpness conjecture for 3-way transportation polytopes.

diam⁡(G(P))=n−d.\operatorname{diam}(G(P))=n-d.

The claim predicts that these transportation polytopes attain the Hirsch bound exactly. The supplied material gives no resolution status.

References
  1. Edward D. Kim, “Geometric Combinatorics of Transportation Polytopes and the Behavior of the Simplex Method”, arXiv:1006.2416 (2010).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.