November 1, 2025
When widths get mean
Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book
Paper says the classic solver is fast; comments fixate on one “mean” word
TLDR: New research argues the classic simplex method can be fast in real-life settings if you analyze it the way it’s actually used. The top comment applauds but nitpicks a confusing term (“mean width”), igniting a precision-vs-practicality debate that’s equal parts useful and hilariously on-brand for math folks.
A new math-meets-code paper claims a win for real-world performance: by analyzing algorithms the way they’re actually built and used, the authors say the vintage “simplex” method—used to optimize plans, budgets, and schedules—runs in reasonable time under practical settings. Cue the community: the very first visible comment basically slammed the brakes on the victory lap to argue about a single term. One reader cheered the work, then zeroed in on a definition of “mean width” that, they say, changes if you move the shape around—translation invariance, for the math-curious—calling it confusing and out of step with how people normally use the word “width.”
That tiny phrase sparked the whole vibe: precision hawks vs. pragmatists. Fans of the paper love the “by the book” idea—model the algorithm the way it’s actually implemented, with the same settings and tolerances—so theory finally matches practice. Meanwhile, the correctness police pounced on the wording like it was a typo in a legal contract. The meme energy? People riffed on “mean width being mean,” and joked this was peak academia: a bold claim about making old tools fast, instantly derailed by a geometry semantics detour. Still, even the nitpickers admit the work is cool. The takeaway: big promise, nerdy bickering, and a reminder that in algorithm-land, the tiniest word can start the loudest fight.
Key Points
- •The paper proposes a new framework called “by the book analysis” that models both input data and algorithm implementation details.
- •The framework is designed to align analytical guarantees with practical behavior observed in implementations and benchmarks.
- •Applied to the simplex method, the approach addresses limitations of smoothed analysis in explaining practical performance.
- •Under input scaling assumptions and feasibility tolerances common in implementations, the simplex method achieves polynomial running time.
- •The analysis bases its assumptions on implementation practices, input modeling best practices, and measurements on benchmark instances.