A key concept in optimization is the combinatorial diameter of a polyhedron. From the point of view of optimization, we would like to relate it to the number of facets \$f\$ and dimension \$d\$ of the polyhedron. In the seminal paper of Klee and Walkup, the Hirsch conjecture, that the bound is \$f-d\$, was shown to be equivalent to several seemingly simpler statements, and was disproved for unbounded polyhedra through the construction of a particular 4-dimensional polyhedron with 8 facets. The Hirsch bound for polytopes was only recently narrowly exceed by Santos.
We consider analogous questions for a variant of the combinatorial diameter called the circuit diameter. In this variant, paths are built from the circuit directions of the polyhedron, and can travel through the interior. We show that many of the Klee-Walkup results and techniques translate to the circuit setting. However, in this setting we are able to verify the 4-dimensional version of a \$d\$-step conjecture for unbounded polytopes, which fails in the combinatorial case.
This is joint work with S. Borgwardt and T. Yusun.