1 citations · 2 across the 8 of their papers we have counts for
5 papers · 1 filter
Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book
Eleon Bach, Alexander E. Black, Sophie Huiberts +1
Narrowing the gap between theory and practice is a longstanding goal of the algorithm analysis community. To further progress our understanding of how algorithms work in practice,…
Optimal Smoothed Analysis of the Simplex Method
Eleon Bach, Sophie Huiberts
Smoothed analysis is a method for analyzing the performance of algorithms, used especially for those algorithms whose running time in practice is significantly better than what can…
Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method
Sophie Huiberts, Yin Tat Lee, Xinzhi Zhang
The simplex method for linear programming is known to be highly efficient in practice, and understanding its performance from a theoretical perspective is an active research topic.…
A nearly optimal randomized algorithm for explorable heap selection
Sander Borst, Daniel Dadush, Sophie Huiberts +1
Explorable heap selection is the problem of selecting the th smallest value in a binary heap. The key values can only be accessed by traversing through the underlying infinite b…
A Friendly Smoothed Analysis of the Simplex Method
Daniel Dadush, Sophie Huiberts
Explaining the excellent practical performance of the simplex method for linear programming has been a major topic of research for over 50 years. One of the most successful framewo…