Talk:Simplex algorithm/Comments

Two important, missing pieces of information: first, this article doesn't mention the idea of a degenerate basis at all. (It does link to Bland's rule, but only at the end, and with no mention of the word degeneracy, so it would be hard for a reader to figure out what Bland's rule is good for.) Second, there have been some recent nice results using smoothed analysis to analyze the complexity of simplex:

http://www.cs.yale.edu/homes/spielman/Research/SimplexStoc.pdf

http://www-math.mit.edu/~spielman/simplex/

http://math.mit.edu/~spielman/SmoothedAnalysis/index.html

The first link above (Kelner & Spielman) shows that there is a randomized version of simplex which runs in (randomized) polynomial time, answering a long-standing open question.

Finally, another important open question is whether there are any strongly polynomial algorithms for solving LPs; it might be worth mentioning this question too.