Hirsch bound conjecture for the circuit diameter of polyhedra
Hirsch bound conjecture for the circuit diameter of polyhedra
Let be an -dimensional polyhedron with facets. Its circuit diameter is the maximum number of maximum-length steps along circuit directions needed to go from one vertex of to another.
Circuit diameter bound. For any -dimensional polyhedron with facets, the circuit diameter is bounded above by
The circuit diameter is an analogue of the combinatorial diameter based on circuit directions and gives a lower bound on the number of augmentation steps under selection rules for linear programming. The analogous Hirsch bound for combinatorial diameter is false in general, so whether it always holds for circuit diameter is the question posed here.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Steffen Borgwardt, Elisabeth Finhold and Raymond Hemmecke, “On the circuit diameter of dual transportation polyhedra”, arXiv:1405.3184 (2014).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.