Researchers Prove 80-Year-Old Optimization Algorithm Has Reached Its Maximum Possible Speed

Computer scientists prove that the simplex method, a fundamental optimization algorithm used across industries for 80 years, has reached its theoretical speed limit and cannot be improved further using current approaches.

• Researchers Sophie Huiberts and Eleon Bach prove that the simplex method, a widely-used optimization algorithm invented by George Dantzig in the 1940s, cannot be improved beyond their newly established runtime limits
• The breakthrough resolves a decades-old theoretical puzzle by showing that feared exponential runtimes do not occur in practice, building on 2001 work by Spielman and Teng that introduced randomness to prevent worst-case scenarios
• The new result demonstrates optimal performance for this approach to the simplex method, though researchers acknowledge that achieving linear scaling would require completely new strategies