Yes, Spielman and Teng showed that the shadow-vertex variation of the simplex method has a smoothed polynomial complexity [1]. It's worth noting that while oth

Yes, Spielman and Teng showed that the shadow-vertex variation of the simplex method has a smoothed polynomial complexity [1]. It's worth noting that while other LP methods are known to be weakly polynomial, the polynomiality depends on the size of the largest coefficient involved in the problem instance rather than on the number of rows and columns of the LP. Finding a purely polynomial algorithm for linear programming or establishing that none exists is a major open question for linear programming, and indeed, for all of mathematics. It's not a Millenium problem, but it's the next best thing [2]. [1] This paper has an even better result, finding a polylogarithmic simplex variant. http://www-personal.umich.edu/~romanv/papers/simplex.pdf http://www-personal.umich.edu/~romanv/papers/simplex.pdf [2] It's Smale problem number 9. http://en.wikipedia.org/wiki/Smale's_problems http://en.wikipedia.org/wiki/Smale's_problems