**Tuesday, 13:45 - 14:10 h, Room: H 3008**

**Nicolai HĂ¤hnle**

An abstract view on the polynomial Hirsch conjecture

**Abstract:**

The question of whether a strongly polynomial algorithm for linear programming exists is one of the great mysteries of the field. It has motivated the polynomial Hirsch conjecture, which claims that the diameter of the vertex-edge graph of every polyhedron is bounded by a polynomial in its affine dimension and the number of facets.

The best known upper-bound on the diameter of polyhedra is a quasi-polynomial bound due to Kalai and Kleitman. What properties of polyhedra make this upper bound work? What techniques could be useful in improving it? We present a purely combinatorial abstraction of the graph of a polyhedron as a way of understanding these questions better. In particular, we present an abstraction in which an almost quadratic construction is known, while the Kalai-Kleitman bound still holds with essentially the same proof.

We made the conjecture that an upper bound of *d(n-1)* holds for this abstraction. We present some evidence for and against this conjecture, and discuss open questions that could guide possible approaches to the polynomial Hirsch conjecture.

Talk 2 of the invited session Tue.2.H 3008

**"Combinatorics and geometry of linear optimization I"** [...]

Cluster 2

**"Combinatorial optimization"** [...]