Polynomial Diameter Conjecture for polytope graphs
For a polytope or polyhedron of dimension with facets, let denote its graph.
Polynomial Diameter Conjecture. Is there a polynomial function such that
The source states that no polynomial upper bound was known for polytope diameters. The conjecture remains open in the supplied material.
References
Primary source
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.