A friendly smoothed analysis of the simplex method

DOI10.1145/3188745.3188826MaRDI QIDQ5230305zbMATH OpenOpenAlexFDO

Authors Daniel Dadush, Sophie Huiberts

Publication date 22 August 2019

Published in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://ir.cwi.nl/pub/27863

zbMATH Keywords

linear programmingshadow vertex simplex methodsmoothed analysis

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Linear programming (90C05) Extreme-point and pivoting methods (90C49)

Recommendations

• A friendly smoothed analysis of the simplex method
• Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method
• 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
• Smoothed analysis of algorithms
• Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time

Cited in

(18)

• Smoothed analysis of termination of linear programming algorithms
• Fast quantum subroutines for the simplex method
• Moser's shadow problem
• The work of Daniel A. Spielman
• Smoothed analysis of algorithms
• scientific article; zbMATH DE number 2119754 (Why is no real title available?)
• The effect of adding randomly weighted edges
• Fast Algorithms for Rank-1 Bimatrix Games
• Smoothed Analysis of the Simplex Method
• Stochastic approximation versus sample average approximation for Wasserstein barycenters
• Smoothing the Gap Between NP and ER
• A friendly smoothed analysis of the simplex method
• Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time
• The Polyhedral Geometry of Pivot Rules and Monotone Paths
• 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
• Smoothed analysis of deterministic discounted and Mean-payoff games
• An unconditional lower bound for the active-set method on the hypercube
• A unified worst case for classical simplex and policy iteration pivot rules

This page was built for publication: A friendly 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 Q5230305)