A Friendly Smoothed Analysis of the Simplex Method
Joint work with Daniel Dadush.
Published in 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018.
In smoothed analysis, we study the running time of an algorithm after adding a small amount of random noise to an arbitrary problem instance. Even if the worst-case running time is bad, the smoothed running time might be good. This would indicate that the worst-case instances are pathological and brittle, thus hopefully explaining good practical performance.
The simplex method is one algorithm for which smoothed analysis was very succesful. In this paper, we significantly improve earlier smoothed complexity bounds. We do this with a much cleaner and simpler proof than previous analyses.
Full version to appear in siopt special issue (invited). Updated June 2019 to include a new algorithm, improving running time when σ is large.