When does Simplex get out of hand?
In 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...