The paper by Spielman and Teng, Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time (JACM 51(3):385–463, 2004), won a Gödel award in 2008.

Since then, has there been a monograph or substantial survey paper written on the subject?

The best I could find was a book chapter in Algorithm Engineering by Müller-Hanneman and Shirra.

  • $\begingroup$ What research have you done? Have you done a literature search? Have you gone to Google Scholar to look at all the articles that cite the one you to mention, to see if any of them meet your criteria? I'd expect you to make a serious effort to exhaust all available ways you could answer the question on your own, before asking here. $\endgroup$
    – D.W.
    Aug 13 '14 at 18:09
  • $\begingroup$ There are many papers on the subject (IEEE Xplore, SpringerLink, ACM Digital Library)... But I was only surprised that Amazon returns no monographies, since the paper won a Gödel award. The award was in 2008 so I am guessing that it is too soon for a monography. $\endgroup$
    – user13675
    Aug 16 '14 at 17:53

To the best of my knowledge, the most recent survey is the following:

Spielman, Daniel A., and Shang-Hua Teng. "Smoothed analysis: an attempt to explain the behavior of algorithms in practice." Communications of the ACM 52.10 (2009): 76-84.

It contains a lot of discussion.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.