Optimal Smoothed Analysis of the Simplex Method
For researchers in linear programming and algorithm analysis, this work establishes the optimal smoothed complexity of the simplex method with respect to noise, resolving a key open question.
The authors prove an upper bound of O(σ^{-1/2} d^{11/4} log(n)^{7/4}) pivot steps for a simplex method under smoothed analysis, improving the previous best bound, and provide a matching lower bound of Ω(σ^{-1/2} d^{1/2} ln(4/σ)^{-1/4}) on the combinatorial diameter, showing optimal noise dependence up to polylog factors.
Smoothed analysis is a method for analyzing the performance of algorithms, used especially for those algorithms whose running time in practice is significantly better than what can be proven through worst-case analysis. Spielman and Teng (STOC '01) introduced the smoothed analysis framework of algorithm analysis and applied it to the simplex method. Given an arbitrary linear program with $d$ variables and $n$ inequality constraints, Spielman and Teng proved that the simplex method runs in time $O(σ^{-30} d^{55} n^{86})$, where $σ> 0$ is the standard deviation of Gaussian distributed noise added to the original LP data. Spielman and Teng's result was simplified and strengthened over a series of works, with the current strongest upper bound being $O(σ^{-3/2} d^{13/4} \log(n)^{7/4})$ pivot steps due to Huiberts, Lee and Zhang (STOC '23). We prove that there exists a simplex method whose smoothed complexity is upper bounded by $O(σ^{-1/2} d^{11/4} \log(n)^{7/4})$ pivot steps. Furthermore, we prove a matching high-probability lower bound of $Ω( σ^{-1/2} d^{1/2}\ln(4/σ)^{-1/4})$ on the combinatorial diameter of the feasible polyhedron after smoothing, on instances using $n = \lfloor (4/σ)^d \rfloor$ inequality constraints. This lower bound indicates that our algorithm has optimal noise dependence among all simplex methods, up to polylogarithmic factors.