Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time

We introduce the smoothed analysis of algorithms, which is a hybrid of the worst-case and average-case analysis of algorithms. Essentially, we study the performance of algorithms under small random perturbations of their inputs. We show that the shadow-vertex simplex algorithm has polynomial smoothed complexity.

• Publication year

  2001

• Venue

  Symposium on the Theory of Computing

• Publication date

  2001-07-06

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/380752.380813arXiv cs/0111050
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems

  2001cited by this paper
• Heuristics for finding large independent sets, with applications to coloring semi-random graphs

  1998cited by this paper
• Deformed products and maximal shadows of polytopes

  1996cited by this paper
• A primal-dual interior point method whose running time depends only on the constraint matrix

  1996cited by this paper
• Linear programming, complexity theory and elementary functional analysis

  1995cited by this paper
• Coloring Random and Semi-Random k-Colorable Graphs

  1995cited by this paper
• Incorporating Condition Measures into the Complexity Theory of Linear Programming

  1995cited by this paper
• Some perturbation theory for linear programming

  1994cited by this paper
• Eigenvalue Roulette and Random Test Matrices

  1993cited by this paper
• A quasi-polynomial bound for the diameter of graphs of polyhedra

  1992influential reference
• A subexponential randomized simplex algorithm (extended abstract)

  1992cited by this paper
• Some Applications of the Rank Revealing QR Factorization

  1992cited by this paper
• A subexponential bound for linear programming

  1992cited by this paper
• Probabilistic Models for Linear Programming

  1991cited by this paper
• A simplex variant solving an m times d linear program in O(min(m2, d2) expected number of pivot steps

  1987cited by this paper
• Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems

  1986cited by this paper
• Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm

  1986cited by this paper
• The Simplex Method: A Probabilistic Analysis

  1986cited by this paper
• Generating Quasi-random Sequences from Semi-random Sources

  1986cited by this paper
• A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension

  1985influential reference
• A new polynomial-time algorithm for linear programming

  1984cited by this paper
• On the average number of steps of the simplex method of linear programming

  1983cited by this paper
• The Problem of the Average Speed of the Simplex Method

  1982influential reference
• Polynomial algorithms in linear programming

  1980cited by this paper
• Computational complexity of parametric linear programming

  1980cited by this paper
• Worst case behavior of the steepest edge simplex method

  1979influential reference
• A polynomial algorithm in linear programming

  1979cited by this paper
• Notes on Bland’s pivoting rule

  1978cited by this paper
• Integral geometry and geometric probability

  1976cited by this paper
• The simplex algorithm with the pivot rule of maximizing criterion improvement

  1973cited by this paper
• Isotropic random simplices

  1971cited by this paper
• HOW GOOD IS THE SIMPLEX ALGORITHM

  1970cited by this paper
• A new approximation for the chi-square integral

  1969cited by this paper
• An Introduction to Probability Theory and Its Applications

  1967cited by this paper
• Handbook of Mathematical Functions.

  1966cited by this paper
• The convex hull of a random set of points

  1965cited by this paper
• über die konvexe Hülle von n zufÄllig gewÄhlten Punkten. II

  1964cited by this paper
• über die konvexe Hülle von n zufällig gewählten Punkten

  1963cited by this paper
• An Introduction to Probability Theory and Its Applications

  1959cited by this paper
• The computational algorithm for the parametric objective function

  1955influential reference

• Kernel-Based Learning of Safety Barriers

  2026cites this paper
• Positive Distribution Shift as a Framework for Understanding Tractable Learning

  2026cites this paper
• Utilitarian Distortion Under Probabilistic Voting

  2026cites this paper
• Finding Short Paths on Simple Polytopes

  2026cites this paper
• Statistical Query Lower Bounds for Smoothed Agnostic Learning

  2026cites this paper
• The Quantum Learning Menagerie (A survey on Quantum learning for Classical concepts)

  2026cites this paper
• High-Probability Polynomial-Time Complexity of Restarted PDHG for Linear Programming

  2025cites this paper
• Multi-Objective Reverse Offloading in Edge Computing for AI Tasks

  2025cites this paper
• Tighter Bounds for the Randomized Polynomial-Time Simplex Algorithm for Linear Programming

  2025cites this paper
• Howard's Policy Iteration is Subexponential for Deterministic Markov Decision Problems with Rewards of Fixed Bit-size and Arbitrary Discount Factor

  2025cites this paper
• A Polytope-Centric Technique for Efficient Domain Partitioning in Function Sorting

  2025cites this paper
• Developing heuristic solution techniques for large-scale unit commitment models

  2025cites this paper
• Radial Isotropic Position via an Implicit Newton’s Method

  2025cites this paper
• An unconditional lower bound for the active-set method on the hypercube

  2025cites this paper
• Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts

  2025cites this paper
• Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks

  2025cites this paper
• Transductive and Learning-Augmented Online Regression

  2025cites this paper
• Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book

  2025cites this paper
• Semi-Random Graphs, Robust Asymmetry, and Reconstruction

  2025cites this paper
• Combining MORL with Restraining Bolts to Learn Normative Behaviour

  2025cites this paper
• Smoothed Analysis of Online Metric Problems

  2025cites this paper
• Online Knapsack Problems with Estimates

  2025cites this paper
• Multi-mode global driving of trapped ions for quantum circuit synthesis

  2025cites this paper
• Smoothed Analysis of Dynamic Graph Algorithms

  2025cites this paper
• Towards Efficient Conversational Recommendations: Expected Value of Information Meets Bandit Learning

  2025cites this paper
• Lower bounds for ranking-based pivot rules

  2025cites this paper
• A Quantum Linear Systems Pathway for Solving Differential Equations

  2025cites this paper
• Oracle Separations for RPH

  2025cites this paper
• Fixed Point Computation: Beating Brute Force with Smoothed Analysis

  2025cites this paper
• Bounds for the number of basic feasible solutions generated by the simplex method with the largest distance rule

  2025cites this paper
• Do financial development and institutional quality impede or stimulate the shadow economy? A comparative analysis of developed and developing countries

  2025cites this paper
• Answering Related Questions

  2025cites this paper
• Experimental results of model predictive control of a coupled tank system using interior-point barrier algorithm

  2025cites this paper
• Learning dynamical systems with hit-and-run random feature maps

  2025cites this paper
• A Programming Language for Feasible Solutions

  2025cites this paper
• New Spectral Algorithms for Refuting Smoothed k-SAT

  2025cites this paper
• Pushing the Complexity Boundaries of Fixed-Point Equations: Adaptation to Contraction and Controlled Expansion

  2025cites this paper
• Learning Local Stackelberg Equilibria from Repeated Interactions with a Learning Agent

  2025cites this paper
• Near-Optimal Tensor PCA via Normalized Stochastic Gradient Ascent with Overparameterization

  2025cites this paper
• The Grand Challenge of Quantum Applications

  2025cites this paper
• How Likely Are Two Voting Rules Different?

  2025cites this paper
• Building an optimal refueling plan using aggregated information about route parameter values from open sources

  2025cites this paper
• Learning Juntas under Markov Random Fields

  2025cites this paper
• Beyond Worst-Case Analysis for Symbolic Computation: Root Isolation Algorithms

  2025cites this paper
• Smoothed analysis in compressed sensing

  2025cites this paper
• Accelerating Graph Similarity Search through Integer Linear Programming

  2025cites this paper
• Quantum Probe Tomography

  2025cites this paper
• Polytope Inner Approximations with Fewer Faces Subject to Minimum-Volume, Point-Inclusion, and Set-Intersection Constraints

  2025cites this paper
• Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information

  2025cites this paper
• Online Learning of Pure States is as Hard as Mixed States

  2025cites this paper
• Smoothed Agnostic Learning of Halfspaces over the Hypercube

  2025cites this paper
• Improved polytope generation for CRC-aided adaptive linear programming polar decoding

  2025cites this paper
• Data-driven Analysis of First-Order Methods via Distributionally Robust Optimization

  2025cites this paper
• Accurately modeling long-term storage with minimum representative hours in large-scale renewable energy systems

  2025cites this paper
• Optimal Smoothed Analysis of the Simplex Method

  2025influential citation
• Optimize or satisfice in engineering design?

  2024cites this paper
• Geometry-dependent matching pursuit: a transition phase for convergence on linear regression and LASSO

  2024cites this paper
• Avoiding Catastrophe in Online Learning by Asking for Help

  2024cites this paper
• Smoothed analysis of deterministic discounted and mean-payoff games

  2024cites this paper
• Oracle-Efficient Differentially Private Learning with Public Data

  2024cites this paper
• A Scheduling Scheme for Minimizing Age Under Delay Tolerance in IoT Systems With Heterogeneous Traffic

  2024cites this paper
• Average gradient outer product as a mechanism for deep neural collapse

  2024cites this paper
• On the optimal objective value of random linear programs

  2024cites this paper
• Exact objectives of random linear programs and mean widths of random polyhedrons

  2024cites this paper
• Mini-batch Submodular Maximization

  2024cites this paper
• Testing Sumsets is Hard

  2024cites this paper
• Exponential Lower Bounds for Many Pivot Rules for the Simplex Method

  2024cites this paper
• On the number of iterations of the DBA algorithm

  2024cites this paper
• A Comprehensive Survey on Delaunay Triangulation: Applications, Algorithms, and Implementations Over CPUs, GPUs, and FPGAs

  2024cites this paper
• Market Making without Regret

  2024cites this paper
• General, efficient, and robust Hamiltonian engineering

  2024cites this paper
• Convergence of $\text{log}(1/\epsilon)$ for Gradient-Based Algorithms in Zero-Sum Games without the Condition Number: A Smoothed Analysis

  2024influential citation
• Clique factors in randomly perturbed graphs: the transition points

  2024cites this paper
• Decentralized Federated Learning With Adaptive Configuration for Heterogeneous Participants

  2024cites this paper
• Smoothed Analysis for Graph Isomorphism

  2024cites this paper
• Pivot Polytopes of Products of Simplices and Shuffles of Associahedra

  2024cites this paper
• Regret Analysis of Bilateral Trade with a Smoothed Adversary

  2024cites this paper
• Average-case optimization analysis for distributed consensus algorithms on regular graphs

  2024cites this paper
• Differentiable Rectilinear Steiner Trees for Analytical Placement

  2024cites this paper
• Smoothed Robustness Analysis: Bridging worst- and average-case robustness analyses via smoothed analysis

  2024cites this paper
• The Better Solution Probability Metric: Optimizing QAOA to Outperform its Warm-Start Solution

  2024cites this paper
• Imbalances in Neurosymbolic Learning: Characterization and Mitigating Strategies

  2024cites this paper
• Pareto Sums of Pareto Sets: Lower Bounds and Algorithms

  2024cites this paper
• A Set Cover Mapping Heuristic for Demand-Robust Fleet Size Vehicle Routing Problem with Time Windows and Compatibility Constraints

  2024cites this paper
• Random Shadows of Fixed Polytopes

  2024cites this paper
• Metric Distortion Under Probabilistic Voting

  2024cites this paper
• Smoothed Online Classification can be Harder than Batch Classification

  2024cites this paper
• Courier routing for a new last-mile logistics service

  2024cites this paper
• On a perturbation analysis of Higham squared maximum Gaussian elimination growth matrices

  2024cites this paper
• Global minimization of a minimum of a finite collection of functions

  2024cites this paper
• Computationally Efficient Reductions Between Some Statistical Models

  2024cites this paper
• New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries

  2024cites this paper
• Online Consistency of the Nearest Neighbor Rule

  2024cites this paper
• Data‐Driven Parameterization Refinement for the Structural Optimization of Cruise Ship Hulls

  2024cites this paper
• A k-swap Local Search for Makespan Scheduling

  2024cites this paper
• Online Simple Knapsack with Bounded Predictions

  2024cites this paper
• Optimization of Network Pavement Life-Cycle Cost: A Piecewise Linearized Approach

  2024cites this paper
• Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning

  2024cites this paper
• Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension

  2024cites this paper
• Impact of climate and geological storage potential on feasibility of hydrogen fuels

  2023cites this paper