patternMinor
Monograph or survey paper on smoothed analysis of algorithms
Viewed 0 times
papersurveyanalysisalgorithmsmonographsmoothed
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#29074, answer score: 2
Revisions (0)
No revisions yet.