Hirsch bound conjecture for the circuit diameter of polyhedra

From papers

Let PP be an nn-dimensional polyhedron with ff facets. Its circuit diameter is the maximum number of maximum-length steps along circuit directions needed to go from one vertex of PP to another.

Circuit diameter bound. For any nn-dimensional polyhedron with ff facets, the circuit diameter is bounded above by

fn.f-n.

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

No solutions have been posted yet.