Smoothed Analysis of Algorithms: Why the Simplex Method Usually Takes Polynomial Time

Title: Smoothed Analysis of Algorithms: Why the Simplex Method Usually Takes Polynomial Time

Research Question: How can we explain the success of algorithms that perform well in practice but are theoretically analyzed as performing poorly?

Methodology: The authors introduce a new method of analysis called "smoothed analysis of algorithms." This method studies the performance of algorithms under small, random perturbations of their inputs. They apply this method to the simplex method, a widely used algorithm for solving linear programming problems.

Results: The authors show that the simplex method has polynomial smoothed complexity. This means that, under small random perturbations of the inputs, the simplex method performs its calculations in a polynomial amount of time.

Implications: This research suggests that the success of the simplex method in practice may be due to its ability to perform well under small, random perturbations of its inputs. This could explain why the simplex method is so effective in solving real-world problems, despite its theoretical limitations.

The research also introduces new techniques and tools for analyzing the performance of algorithms, which could be applied to other algorithms and problems in computer science and related fields.

Link to Article: https://arxiv.org/abs/0111050v1 Authors: arXiv ID: 0111050v1