A friendly smoothed analysis of the simplex method

DOI10.1145/3188745.3188826zbMath1427.90199OpenAlexW2770074417MaRDI QIDQ5230305

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 programmingsmoothed analysisshadow vertex simplex method

Mathematics Subject Classification ID

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

Related Items (8)

Stochastic approximation versus sample average approximation for Wasserstein barycenters ⋮ Smoothing the Gap Between NP and ER ⋮ The Polyhedral Geometry of Pivot Rules and Monotone Paths ⋮ A Friendly Smoothed Analysis of the Simplex Method ⋮ Fast quantum subroutines for the simplex method ⋮ The Effect of Adding Randomly Weighted Edges ⋮ Fast Algorithms for Rank-1 Bimatrix Games ⋮ Moser's shadow problem

This page was built for publication: A friendly smoothed analysis of the simplex method