Smoothed Analysis:
Motivation and Discrete Models
Authors:
Daniel A. Spielman, and
Shang-Hua Teng .
Bibliographic Information:
In the proceedings of WADS 2003, Lecture Notes in Computer Science,
Springer-Verlag.
Abstract
In smoothed analysis, one measures the complexity of algorithms assuming
that their inputs are subject to small amounts of random noise.
In an earlier work
(Spielman and Teng, 2001)
, we introduced this analysis
to explain the good practical behavior
of the simplex algorithm.
In this paper, we provide further motivation for the smoothed analysis
of algorithms, and develop models of noise
suitable for analyzing the behavior of discrete algorithms.
We then consider the smoothed complexities of testing some simple
graph properties in these models.
You can download this paper as
Postscript,
compressed Postscript,
PDF, or
compressed PDF.
Daniel A. Spielman
Last modified: Fri Aug 3 00:21:05 EDT 2001