Smoothed Analysis: Why The Simplex Algorithm Usually Takes Polynomial Time.

Authors: Daniel A. Spielman and Shang-Hua Teng

Bibliographic Information: Journal of the ACM, Vol 51 (3), pp. 385 - 463, 2004.


The main differences between the journal version and the one available at ArXiv are: These versions substantially improve upon the result claimed in the extended abstract, which appeared in STOC '01.

For more information on smoothed analysis, check out the Smoothed Analysis Homepage.


You can download the ArXiv version of the full paper in the following formats:


Daniel A. Spielman
Last modified: Wed May 11 12:25:23 EDT 2005