Smoothed Analysis of the Simplex Method

DOI10.1017/9781108637435.019MaRDI QIDQ5027280zbMATH OpenOpenAlexFDO

Authors Daniel Dadush, Sophie Huiberts

Publication date 4 February 2022

Full work available at URL https://www.cambridge.org/core/books/beyond-the-worstcase-analysis-of-algorithms/smoothed-analysis-of-the-simplex-method/690B9CB808AFBE8B6333B83731375404

Mathematics Subject Classification ID

Analysis of algorithms (68W40)

Recommendations

• A friendly smoothed analysis of the simplex method
• A friendly smoothed analysis of the simplex method
• Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time
• Smoothed analysis of algorithms
• Linear optimization with the shadow vertex algorithm in the context of probabilistic analyses. Studies on the transition from phase 1 to phase 2 in the average-case analysis and in the smoothing analysis of the simplex method

Cited in

(4)

• Smoothed analysis of algorithms
• Upper and lower bounds on the smoothed complexity of the simplex method
• Upper and lower bounds on the smoothed complexity of the simplex method
• Analysis of a smoothing method for symmetric conic linear programming

This page was built for publication: Smoothed Analysis of the Simplex Method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5027280)