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

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

詳細記述

書誌詳細
出版年:Journal of the ACM 51, 3 (2004).
第一著者: Spielman, Daniel A.
フォーマット: 論文
言語:English
主題:
Theory of computation.
Analysis of algorithms and problem complexity.
Numerical algorithms and problems.
Mathematics of computing.
Numerical analysis.
Optimization.
Linear programming.
Algorithms.
Theory.