Optimal Smoothed Analysis of the Simplex Method

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 = ⌊(4/σ) d ⌋ inequality constraints. This lower bound indicates that our algorithm has optimal noise dependence among all simplex methods, up to polylogarithmic factors.