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...

Ausführliche Beschreibung

Bibliographische Detailangaben

Veröffentlicht in:	Journal of the ACM 51, 3 (2004).
1. Verfasser:	Spielman, Daniel A.
Format:	Artikel
Sprache:	English
Schlagworte:	Theory of computation. Analysis of algorithms and problem complexity. Numerical algorithms and problems. Mathematics of computing. Numerical analysis. Optimization. Linear programming. Algorithms. Theory.