Discussion
Loading...

#Tag

  • About
  • Code of conduct
  • Privacy
  • Users
  • Instances
  • About Bonfire
Hacker News
@h4ckernews@mastodon.social  ·  activity timestamp 2 weeks ago

Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book

https://arxiv.org/abs/2510.21613

#HackerNews #BeyondSmoothedAnalysis #SimplexMethod #AlgorithmResearch #Arxiv #Mathematics

arXiv.org

Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book

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 that we call by the book analysis. 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. 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 explain how our framework overcomes several weaknesses of smoothed analysis and 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.
  • Copy link
  • Flag this post
  • Block
Log in

bonfire.cafe

A space for Bonfire maintainers and contributors to communicate

bonfire.cafe: About · Code of conduct · Privacy · Users · Instances
Bonfire social · 1.0.0 no JS en
Automatic federation enabled
  • Explore
  • About
  • Members
  • Code of Conduct
Home
Login