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

Mô tả đầy đủ

Chi tiết về thư mục
Xuất bản năm:Journal of the ACM 51, 3 (2004).
Tác giả chính: Spielman, Daniel A.
Định dạng: Bài viết
Ngôn ngữ:English
Những chủ đề:
Theory of computation.
Analysis of algorithms and problem complexity.
Numerical algorithms and problems.
Mathematics of computing.
Numerical analysis.
Optimization.
Linear programming.
Algorithms.
Theory.