On the Existence of a Short Admissible Pivot Sequence for Feasibility and Linear Optimization Problems
Kouki Fukuda, Tamás Terlaky · 1999
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. An admissible pivot is a common generalization of simplex and dual simplex pivots, and there are various admissible pivot methods that are finite, including the least-index criss-cross method. No polynomial admissible algorithm is known. 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). More precisely, we extend the existence result due to Fukuda, Luthi and Namiki for nondegeneate LPs. 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...