(home)   //   (publications)   //   (blog)   //   (scans from the library)

A Friendly Smoothed Analysis of the Simplex Method

PDF

arXiv

BibTeX

@article{DH17,
author = {Dadush, Daniel and Huiberts, Sophie},
title = {A Friendly Smoothed Analysis of the Simplex Method},
journal = {SIAM Journal on Computing},
volume = {49},
archivePrefix={arXiv},
eprint={1711.05667},
number = {5},
pages = {STOC18-449--499},
year = {2020},
doi = {10.1137/18M1197205},
note = {preliminary version in STOC 2018}
}
Beyond Smoothed Analysis: Analyzing the Simplex Method By-the-Book (Oct 2025)
Eleon Bach, Alexander Black, Sean Kafer
STOC 2026 / arXiv / code / talk / bibTeX
Optimal Smoothed Analysis of the Simplex Method (May 2025)
Eleon Bach
FOCS 2025 / arXiv / video / bibTeX
Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method (Nov 2022)
Xinzhi Zhang, Yin Tat Lee
STOC 2023, TheoretiCS / arXiv / video / bibTeX
Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes (Dec 2021)
Gilles Bonnet, Daniel Dadush, Uri Grupel, Sophie Huiberts, Galyna Livshyts.
SOCG 2022, Discrete and Computational Geometry / arXiv / talk / bibTeX
A Friendly Smoothed Analysis of the Simplex Method (Nov 2017)
Daniel Dadush, Sophie Huiberts.
STOC 2018, SIAM Journal on Computing / arXiv / talk / bibTeX