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, we propose a new algorithm analysis framework called by the book analysis. Unlike earlier frameworks, by the book analysis models not only the algorithm's input data but also the algorithm itself. Results from this framework are intended to correspond well with established knowledge of an algorithm's practical behavior, grounded in observations from implementations, best practices in input modeling, and measurements on practical benchmark instances.
We apply our framework to the simplex method, an algorithm known for its excellent performance in practice and notorious for its high running time under worst-case analysis. The simplex method also showcased the state-of-the-art framework smoothed analysis (Spielman and Teng, STOC'01). We explain how our framework overcomes several weaknesses of smoothed analysis and prove that under input scaling assumptions, feasibility tolerances, and other design principles used by simplex method implementations, the simplex method indeed attains polynomial running time.
Blogger's Review: This new by the book analysis framework offers a fresh perspective on algorithm evaluation, particularly in assessing practical performance, addressing the shortcomings of traditional theoretical analysis. The proof of polynomial time complexity for the simplex method provides theoretical support for its widespread application in real-world scenarios, making it a noteworthy contribution.