Smoothed analysis of algorithms Why the simplex algorithm usually takes polynomial time.

We introduce the smoothed analysis of algorithms, which continuously interpolates between the worst-case and average-case analyses of algorithms. In smoothed analysis, we measure the maximum over inputs of the expected performance of an algorithm under small random perturbations of that input. We me...

Full description

Bibliographic Details

Published in:	Journal of the ACM 51, 3 (2004).
Main Author:	Spielman, Daniel A.
Format:	Article
Language:	English
Subjects:	Theory of computation. Analysis of algorithms and problem complexity. Numerical algorithms and problems. Mathematics of computing. Numerical analysis. Optimization. Linear programming. Algorithms. Theory.