Optimal Smoothed Analysis of the Simplex Method
Eleon Bach, Sophie Huiberts · 2025
Read Optimal Smoothed Analysis of the Simplex Method by Eleon Bach, Sophie Huiberts (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-04197.txt.
Introduction
Eleon Bach and Sophie Huiberts settle the smoothed performance of the simplex method in a 2025 paper. The simplex method solves linear programs fast in practice, yet worst-case bounds look poor. Smoothed analysis bridges the gap by adding small random noise to the input and measuring typical run time.
Earlier work cut the bound step by step over two decades. Bach and Huiberts now give a method whose smoothed step count improves on the best prior bound. They also prove a matching lower bound on the width of the feasible region after smoothing. That pairing shows their noise dependence is the best any simplex variant can reach, apart from small log factors.
Catalog record
| CREATOR | Eleon Bach, Sophie Huiberts |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 144 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-04197