Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time

2001/11/19 by Daniel A. Spielman, Shang-Hua Teng, Shang‐Hua Teng +2 · 2 voices · 18 citations
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #G.1.6 #Numerical Methods and Algorithms #Polynomial and algebraic computation #cs.DS

paper · pdf · doi:10.48550/arxiv.cs/0111050

openalex publication_date 2001/11/19 · arxiv published 2001/11/19 · arxiv updated 2003/10/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We introduce the smoothed analysis of algorithms, which is a hybrid of the worst-case and average-case analysis of algorithms. In smoothed analysis, we measure the maximum over inputs of the expected performance of an algorithm under small random perturbations of that input. We measure this performance in terms of both the input size and the magnitude of the perturbations. We show that the simplex algorithm has polynomial smoothed complexity.

Cited by

• Bitcoin Mempool Linearization
• Lower bounds for ranking-based pivot rules
• Accurately modeling long-term storage with minimum representative hours in large-scale renewable energy systems
• Data-Driven Analysis of First-Order Methods via Distributionally Robust Optimization
• Smoothed Agnostic Learning of Halfspaces over the Hypercube
• Tighter Bounds for the Randomized Polynomial-Time Simplex Algorithm for Linear Programming
• The Grand Challenge of Quantum Applications
• Accelerating Graph Similarity Search through Integer Linear Programming
• Randomizing the Number of Centers in k-means++
• Learning Local Stackelberg Equilibria from Repeated Interactions with a Learning Agent
• Near-Optimal Tensor PCA via Normalized Stochastic Gradient Ascent with Overparameterization
• Quantum Probe Tomography
• A Quantum Linear Systems Pathway for Solving Differential Equations
• Transductive and Learning-Augmented Online Regression
• Semi-Random Graphs, Robust Asymmetry, and Reconstruction
• A Programming Language for Feasible Solutions
• Smoothed Analysis of Online Metric Problems
• Bounds for the number of basic feasible solutions generated by the simplex method with the largest distance rule

Discussions

• Why the Simplex Algorithm Usually Takes Polynomial Time (2001) [hn, 3 points, 0 comments]
• You might be looking for smoothed analysis (en.wikipedia.org/wiki/Smoothe...)? Kind of interpolates between worst and average-case: no distribution over problem instances you have to specify but ignor [bsky, 2 points, 1 comments]

Related

• Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book
• Smoothed analysis of algorithms
• Optimal Smoothed Analysis of the Simplex Method
• Smoothed Complexity Theory
• Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method