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:

The theorem and lemma numbers are different
The ArXiv version has a table of contents and index, which the ACM refused to publish

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:

Last modified: Wed May 11 12:25:23 EDT 2005