Smoothed Analysis of Algorithms: Why the SimplexAlgorithm Usually Takes Polynomial TimeDANIEL A. SPIELMANMassachusetts Institute of Technology, Boston, MassachusettsANDSHANG-HUA TENGBoston University, Boston, Massachusetts, and Akamai Technologies, Inc.Abstract. We introduce the smoothed analysis of algorithms, which continuously interpolates be-tween the worst-case and average-case analyses of algorithms. In smoothed analysis, we measure themaximum over inputs of the expected performance of an algorithm under small random perturbationsof that input. We measure this performance in terms of both the input size and the magnitude of theperturbations. We show that the simplex algorithm has smoothed complexity polynomial in the inputsize and the standard deviation of Gaussian perturbations.Categories and Subject Descriptors: F.2.1 [Analysis of Algorithms and ProblemsComplexity]: Nu-merical Algorithms and Problems; G.1.6 [Numerical Analysis]: Optimization—linear programmingGeneral Terms: Algorithms, TheoryAdditional Key Words and Phrases: Simplex method, smoothed analysis, complexity, perturbation1. IntroductionThe Analysis of Algorithms community has been challenged by the existence ofremarkable algorithms that are known by scientists and engineers to work wellA preliminary version of this article was published in the Proceedings of the 33rd Annual ACMSymposium on Theory of Computing (Hersonissos, Crete, Greece, July 6–8). ACM, New York, 2001,pp. 296–305.D. Spielman’s work at M.I.T. was partially supported by an Alfred P. Sloan Foundation Fellowship,NSF grants No. CCR-9701304 and CCR-0112487, and a Junior Faculty Research Leave sponsoredby the M.I.T. School of ScienceS.-H. Teng’s work was done at the University of Illinois at Urbana-Champaign, Boston University,and while visiting the Department of Mathematics at M.I.T. His work was partially supported by anAlfred P. Sloan Foundation Fellowship, and NSF grant No. CCR: 99-72532.Authors’ addresses: D.A.Spielman, Department of Mathematics, Massachusetts Institute of Technol-ogy, Cambridge, MA 02139, e-mail: [email protected]; S.-H. Teng, Department of ComputerScience, Boston University, Boston, MA 02215.Permission to make digital or hard copies of part or all of this work for personal or classroom use isgranted without fee provided that copies are not made or distributed for profit or direct commercialadvantage and that copies show this notice on the first page or initial screen of a display along with thefull citation. Copyrights for components of this work owned by others than ACM must be honored.Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, to redistributeto lists, or to use any component of this work in other works requires prior specific permission and/ora fee. Permissions may be requested from Publications Dept., ACM, Inc., 1515 Broadway, New York,NY 10036 USA, fax: +1 (212) 869-0481, or [email protected]°2004 ACM 0004-5411/04/0500-0385 $5.00Journal of the ACM, Vol. 51, No. 3, May 2004, pp. 385–463.386 D. A. SPIELMAN AND S.-H. TENGin practice, but whose theoretical analyses are negative or inconclusive. The rootof this problem is that algorithms are usually analyzed in one of two ways: byworst-case or average-case analysis. Worst-case analysis can improperly suggestthat an algorithm will perform poorly by examining its performance under themost contrived circumstances. Average-case analysis was introduced to providea less pessimistic measure of the performance of algorithms, and many practicalalgorithms perform well on the random inputs considered in average-case analysis.However, average-case analysis may be unconvincing as the inputs encountered inmany application domains may bear little resemblance to the random inputs thatdominate the analysis.We propose ananalysis thatwe call smoothed analysis which can help explainthesuccess of algorithms that have poor worst-case complexity and whose inputs looksufficiently different from random that average-case analysis cannot be convinc-ingly applied. In smoothed analysis, we measure the performance of an algorithmunder slight random perturbations of arbitrary inputs. In particular, we considerGaussian perturbations of inputs to algorithms that take real inputs, and we mea-sure the running times of algorithms in terms of their input size and the standarddeviation of the Gaussian perturbations.We show that the simplex method has polynomial smoothed complexity. Thesimplex method is the classic example of an algorithm that is known to performwell in practice but which takes exponential time in the worst case [Klee andMinty 1972; Murty 1980; Goldfarb and Sit 1979; Goldfarb 1983; Avis and Chv´atal1978; Jeroslow 1973; Amenta and Ziegler 1999]. In the late 1970s and early 1980sthe simplex method was shown to converge in expected polynomial time on var-ious distributions of random inputs by researchers including Borgwardt, Smale,Haimovich, Adler, Karp, Shamir, Megiddo, and Todd [Borgwardt 1980; Borgwardt1977; Smale 1983; Haimovich 1983; Adler et al. 1987; Adler and Megiddo 1985;Todd 1986]. These works introduced novel probabilistic tools to the analysis ofalgorithms, and provided some intuition as to why the simplex method runs soquickly. However, these analyses are dominated by “random looking” inputs: evenif one were to prove very strong bounds on the higher moments of the distributionsof running times on random inputs, one could not prove that an algorithm performswell in any particular small neighborhood of inputs.To bound expected running times on small neighborhoods of inputs, we considerlinear programming problems in the formmaximizezTxsubject to Ax ≤ y , (1)and prove that for every vectorz and every matrix¯A and vector ¯y, the expectationover standard deviation σ (maxik(¯yi, ¯ai)k) Gaussian perturbations A and y of¯Aand ¯y of the time taken by a two-phase shadow-vertex simplex method to solvesuch a linear program is polynomial in 1/σ and the dimensions ofA.1.1. LINEAR PROGRAMMING AND THE SIMPLEX METHOD. It is difficult to over-state the importance of linear programming to optimization. Linear programmingproblems arise in innumerable industrial contexts. Moreover, linear programmingis often used as a fundamental step in other optimization algorithms. In a linearprogramming problem, one is asked to maximize or minimize a linear function overa polyhedral region.Smoothed Analysis of Algorithms 387Perhaps one