3 papers
cs.DS2025
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,…
cs.DM2025
An Unconditional Lower Bound for the Active-Set Method in Almost-Linear Programming
Eleon Bach, Yann Disser, Sophie Huiberts +1
We prove that, for every fixed , the active-set method requires exponentially many iterations in the worst case to maximize a convex objective of the form $(x_1)^{1+ε}+\…
cs.DS2025
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…