Smoothed Analysis of Algorithms:
presented at ICM 2002.
Authors:
Daniel A. Spielman, and
Shang-Hua Teng .
Bibliographic Information:
To appear in Volume I of the proceedings of the
2002 International Congress of Mathematicians.
Abstract
Spielman and Teng~[STOC '01] introduced the smoothed analysis of
algorithms to provide a framework in which one could
explain the
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
Postscript,
PDF,
Compressed Postscript, or
Compressed PDF,
Daniel A. Spielman
Last modified: Sun Sep 8 13:04:42 EDT 2002