Department of Mathematics

Title: Department of Mathematics

Research Question: The main research question of this paper is to analyze the complexity of the Simplex Method, a widely used algorithm for solving linear programming problems. The authors want to know if this method has polynomial smoothed complexity, which is a hybrid of the worst-case and average-case analysis of algorithms.

Methodology: The authors introduce the concept of "smoothed analysis of algorithms," which measures the maximum over inputs of the expected performance of an algorithm under small random perturbations of that input. They use vector and matrix norms, probability theory, and changes of variables to develop their method.

Results: The authors present a two-phase method for solving linear programming problems, which they believe can be extended to provide polynomial smoothed complexity for the Simplex Method. They also provide bounds on the shadow of LP+ and LP', which are used in their analysis.

Implications: If the authors' results hold, it would mean that the Simplex Method has polynomial smoothed complexity, which would be a significant advancement in the field of algorithm analysis. This could have practical implications for the efficiency of the method and potentially lead to further improvements in algorithm design and analysis.

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