A randomized polynomial-time simplex algorithm for linear programming.

Jonathan A. Kelner, Daniel A. Spielman

Browse the full STOC paper archive.