When does Simplex get out of hand?
September 22nd, 2004In 1972, Klee and Minty gave an example of a linear programming problem in which the polytope P is a distortion of an n-dimensional cube. They showed that the simplex method as formulated by Danzig visits all 2n vertices before arriving at the optimal vertex.
This is a quote from wikipedia. Maybe I should dig up that paper…