Polynomial Diameter Conjecture for polytope graphs
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.