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