ABSTRACT
This chapter shows that the simplex algorithm run in polynomial time, but a different one, the ellipsoid algorithm, does solve linear programs in polynomial time. In dimensions, the instance is shaped roughly like an dimensional cube for which the simplex method travels through every vertex to reach the optimum. One could modify the traditional simplex method so as to solve the Klee-Minty example in a single iteration. However, Jeroslow subsequently proved that for that selection rule, and for many other rules that depend only on values in the current tableau, there exist instances for which the simplex method takes exponentially many steps. Let's specify the sequence of vertices that we want the simplex method to traverse. The simplex method with the greatest-reduced-cost rule for the entering variable is not a polynomial-time algorithm. The presents the first breakthrough, the ellipsoid algorithm.
