Title: Analyzing the Simplex Method by the Book

Speaker: Eleon Bach
Technical University of Munich

Summary:
Narrowing the gap between theory and practice is a longstanding goal of the algorithm analysis community. In this talk we discuss the new by the book algorithm analysis framework.
In contrast to earlier frameworks, by the book analysis not only models an algorithm’s input data, but also the algorithm itself. Results from by the book analysis are meant to correspond well with established knowledge of an algorithm’s practical behavior, as they are meant to be grounded in observations from implementations, input modeling best practices, and measurements on practical benchmark instances.
Furthermore, we apply our framework to the simplex method, an algorithm which is beloved for its excellent performance in practice and notorious for its high running time under worst-case analysis.
The simplex method similarly showcased the state of the art framework smoothed analysis (Spielman and Teng, STOC’01).
We prove that under input scaling assumptions, feasibility tolerances and other design principles used by simplex method implementations, the simplex method indeed attains a polynomial running time. This is joint work with Alexander Black, Sophie Huiberts and Sean Kafer.

Bio:
Eleon Bach is a PhD student at TU Munich. Their research focusses on the analysis of practical algorithms such as the simplex algorithm. Eleon’s research was featured by the Quanta magazine and WIRED.

—
This event is Zoom only:
JOIN VIA ZOOM WITH MEETING ID: 873 1557 5255; PASSWORD: 778635

SEMINAR: WED 08 APRIL 2026 17:00-18:00 (AEST, Melbourne)/ 09:00-10:00 (CEST)
Please note seminar time to accommodate different timezones.