On the Admissible Pivot Hirsch Conjecture: Short admissible pivot sequences for the linear optimization problems do exist
Tamás Terlaky, Lehigh University

Finding a pivot rule for the simplex method that is strongly polynomial is an open question. In fact, the shortest length of simplex pivots from any feasible basis to some optimal basis is not known to be polynomially bounded, even the polynomial Hirsch conjecture is still unsolved. Here we are concerned with admissible pivots, that are common generalization of primal and dual simplex pivots. The key question we address here is the existence of a short sequence of admissible pivots, where short means linear in the basis and nonbasis sizes.
For the feasibility problem, we prove the existence of a short admissible pivot sequence from an arbitrary basis to a feasible basis. Furthermore, for the general LP, the existence of a short admissible pivot sequence from an arbitrary basis to an optimal basis is proved without any nondegeneracy assumptions. Although this result yields a solution to what we may call an "Admissible Pivot Hirsch Conjecture", still, the question remains: is it possible to design a strongly polynomial admissible pivot algorithm?
Joint work with Komei Fukuda, ETH Zurich, Switzerland