Motivation and Discrete Models
Daniel A. Spielman, and
Shang-Hua Teng .
In the proceedings of WADS 2003, Lecture Notes in Computer Science,
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
Daniel A. Spielman
Last modified: Fri Aug 3 00:21:05 EDT 2001