Department of Mathematics

Title: Department of Mathematics

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

Methodology: The authors introduce the concept of smoothed analysis of algorithms, which measures the maximum performance of an algorithm under small random perturbations of the input. They use geometric definitions, vector and matrix norms, probability theory, and Gaussian random vectors to analyze the simplex algorithm. They also use changes of variables to simplify the problem.

Results: The authors present a two-phase method for the simplex algorithm, which involves an initial pivot phase and a subsequent optimization phase. They prove that the shadow size, which is a measure of the difficulty of the problem, is bounded, leading to polynomial smoothed complexity for the simplex algorithm.

Implications: The results of this paper have significant implications for the field of computer science and operations research. The polynomial smoothed complexity of the simplex algorithm suggests that this method can be used to solve large-scale linear programming problems efficiently. The authors also discuss practicality of their analysis, further analysis of the simplex algorithm, and open questions related to smoothed analysis.

Conclusion: In conclusion, the authors have introduced a new method for analyzing the complexity of algorithms, called smoothed analysis, and applied it to the simplex algorithm. They have shown that the simplex algorithm has polynomial smoothed complexity, which has important implications for the field of computer science and operations research.

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