Invited Session Tue.2.H 3008

Tuesday, 13:15 - 14:45 h, Room: H 3008

Cluster 2: Combinatorial optimization [...]

Combinatorics and geometry of linear optimization I


Chair: Antoine Deza and Jesus Antonio De Loera



Tuesday, 13:15 - 13:40 h, Room: H 3008, Talk 1

Francisco Santos
Counter-examples to the Hirsch conjecture


About two years ago I announced the first counter-example to
the (bounded) Hirsch conjecture: a 43-dimensional polytope
with 86 facets and diameter (at least) 44. It was based on
the construction of a 5-prismatoid of "width'' 6, with 48
vertices. Since then, some improvements or related results
have been obtained: S.-Stephen-Thomas showed that prismatoids
of dimension 4 cannot lead to non-Hirsch polytopes, and
S.-Matschke-Weibel constructed smaller 5-prismatoids of
length 6, now with only 25 facets. These produce
counter-examples to the Hirsch conjecture in dimension 20.
But, all in all, the main problem underlying the Hirsch
Conjecture remains as open as before. In particular, it would
be very interesting to know the answer to any of the following

  1. Is there a polynomial bound f(n) for the diameter of
    n-faceted polytopes? ("Polynomial Hirsch Conjecture'').
  2. Is there a linear bound? Is f(n)=2n such a bound?

A conjecture of Hänle, suggested by the work of Eisenbrand et
al. in the abstract setting of "connected layer sequences''
would imply that nd is an upper bound.



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

Nicolai Hähnle
An abstract view on the polynomial Hirsch conjecture


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.



Tuesday, 14:15 - 14:40 h, Room: H 3008, Talk 3

Yuriy Zinchenko
Polytopes and arrangements: Diameter and curvature

Coauthors: Antoine dDeza, Tamas Terlaky


We introduce a continuous analogue of the Hirsch conjecture and a discrete analogue of the result of Dedieu, Malajovich and Shub. We prove a continuous analogue of the result of Holt and Klee, namely, we construct a family of polytopes which attain the conjectured order of the largest total curvature, and a continuous analogue of a d-step equivalence result for the diameter of a polytope. Potential extensions of this work will be highlighted.


  In particular, Payday Loans Texas can cater to the needs of its residents. In this section we give only a brief summary recommendation for admission of Canadian Levitra. Full information can be found in the instructions for receiving medications with vardenafil.