Smoothed Analysis of Algorithms:
presented at ICM 2002.
Daniel A. Spielman, and
Shang-Hua Teng .
To appear in Volume I of the proceedings of the
2002 International Congress of Mathematicians.
Spielman and Teng~[STOC '01] introduced the smoothed analysis of
algorithms to provide a framework in which one could
success in practice of algorithms and heuristics that could not be
understood through the traditional worst-case and average-case analyses.
In this talk, we survey some of the smoothed analyses that have been performed.
You can download this paper as
Compressed Postscript, or
Daniel A. Spielman
Last modified: Sun Sep 8 13:04:42 EDT 2002