More Web Proxy on the site http://driver.im/

article

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

Authors:

Daniel A. Spielman,

Shang-Hua TengAuthors Info & Claims

Journal of the ACM (JACM), Volume 51, Issue 3

Pages 385 - 463

https://doi.org/10.1145/990308.990310

Published: 01 May 2004 Publication History

Abstract

We introduce the smoothed analysis of algorithms, which continuously interpolates between the worst-case and average-case analyses 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 smoothed complexity polynomial in the input size and the standard deviation of Gaussian perturbations.

References

[1]

Abramowitz, M., and Stegun, I. A., Eds. 1970. Handbook of Mathematical Functions, 9 ed. Applied Mathematics Series, vol. 55. National Bureau of Standards.

[2]

Adler, I. 1983. The expected number of pivots needed to solve parametric linear programs and the efficiency of the self-dual simplex method. Tech. Rep., University of California at Berkeley. May.

[3]

Adler, I., Karp, R. M., and Shamir, R. 1987. A simplex variant solving an m x d linear program in O(min(m2,d2)) expected number of pivot steps. J. Complex. 3, 372--387.

[4]

Adler, I., and Megiddo, N. 1985. A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension. J. ACM 32, 4 (Oct.), 871--895.

[5]

Amenta, N., and Ziegler, G. 1999. Deformed products and maximal shadows of polytopes. In Advances in Discrete and Computational Geometry, B. Chazelle, J. Goodman, and R. Pollack, Eds. Number 223 in Contemporary Mathematics. American Mathematics Society, 57--90.

[6]

Avis, D., and Chvátal, V. 1978. Notes on Bland's pivoting rule. In Polyhedral Combinatorics. Math. Programming Study, vol. 8. 24--34.

[7]

Blaschke, W. 1935. Integralgeometrie 2: Zu ergebnissen von M. W. Crofton. Bull. Math. Soc. Roumaine Sci. 37, 3--11.

[8]

Blum, A., and Spencer, J. 1995. Coloring random and semi-random k-colorable graphs. J. Algorithms 19, 2, 204--234.

[9]

Borgwardt, K. H. 1977. Untersuchungen zur asymptotik der mittleren schrittzahl von simplexverfahren in der linearen optimierung. Ph.D. dissertation, Universitat Kaiserslautern.

[10]

Borgwardt, K. H. 1980. The Simplex Method: a probabilistic analysis. Number 1 in Algorithms and Combinatorics. Springer-Verlag, New York.

[11]

Chan, T. F., and Hansen, P. C. 1992. Some applications of the rank revealing QR factorization. SIAM J. Sci. Stat. Comput. 13, 3 (May), 727--741.

[12]

Dantzig, G. B. 1951. Maximization of linear function of variables subject to linear inequalities. In Activity Analysis of Production and Allocation, T. C. Koopmans, Ed. 339--347.

[13]

Edelman, A. 1992. Eigenvalue roulette and random test matrices. In Linear Algebra for Large Scale and Real-Time Applications, M. S. Moonen, G. H. Golub, and B. L. R. D. Moor, Eds. NATO ASI Series. 365--368.

[14]

Efron, B. 1965. The convex hull of a random set of points. Biometrika 52, 3/4, 331--343.

[15]

Feige, U., and Kilian, J. 1998. Heuristics for finding large independent sets, with applications to coloring semi-random graphs. In 39th Annual Symposium on Foundations of Computer Science: Proceedings (Palo Alto, Calif. Nov. 8--11). IEEE Computer Society Press, Los Alamitos, Calif.

[16]

Feige, U., and Krauthgamer, R. 1998. Improved performance guarantees for bandwidth minimization heuristics. http://www.cs.berkeley.edu/&sim;robi/papers/FK-BandwidthHenristics-manuscript98.ps.gz.

[17]

Feller, W. 1968. An Introduction to Probability Theory and Its Applications. Vol. 1. Wiley, New York.

[18]

Feller, W. 1971. An Introduction to Probability Theory and Its Applications. Vol. 2. Wiley, New York.

[19]

Goldfarb, D. 1983. Worst case complexity of the shadow vertex simplex algorithm. Tech. Rep. Columbia Univ., New York.

[20]

Goldfarb, D., and Sit, W. T. 1979. Worst case behaviour of the steepest edge simplex method. Disc. Appl. Math 1, 277--285.

[21]

Haimovich, M. 1983. The simplex algorithm is very good!: On the expected number of pivot steps and related properties of random linear programs. Tech. Rep. Columbia Univ., New York.

[22]

Jeroslow, R. G. 1973. The simplex algorithm with the pivot rule of maximizing improvement criterion. Disc. Math. 4, 367--377.

[23]

Kalai, G. 1992. A subexponential randomized simplex algorithm. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (Victoria, B.C., Canada). ACM, New York, 475--482.

[24]

Kalai, G., and Kleitman, D. J. 1992. A quasi-polynomial bound for the diameter of graphs of polyhedra. Bull. Amer. Math. Soc. 26, 315--316.

[25]

Karmarkar, N. 1984. A new polynomial time algorithm for linear programming. Combinatorica 4, 373--395.

[26]

Khachiyan, L. G. 1979. A polynomial algorithm in linear programming. Doklady Akademia Nauk SSSR, 1093--1096.

[27]

Klee, V., and Minty, G. J. 1972. How good is the simplex algorithm? In Inequalities---III, Shisha, O., Ed. Academic Press, Orlando, Fla., 159--175.

[28]

Matoušek, J., Sharir, M., and Welzl, E. 1996. A subexponential bound for linear programming. Algorithmica 16, 4/5 (Oct./Nov.), 498--516.

[29]

Megiddo, N. 1986. Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm. Math. Prog. 35, 2, 140--172.

[30]

Miles, R. E. 1971. Isotropic random simplices. Adv. Appl. Prob. 3, 353--382.

[31]

Murty, K. G. 1980. Computational complexity of parametric linear programming. Math. Prog. 19, 213--219.

[32]

Renegar, J. 1994. Some perturbation theory for linear programming. Math. Prog. Ser. A. 65, 1, 73--91.

[33]

Renegar, J. 1995a. Incorporating condition measures into the complexity theory of linear programming. SIAM J. Optim. 5, 3, 506--524.

[34]

Renegar, J. 1995b. Linear programming, complexity theory and elementary functional analysis. Math. Prog. Ser. A. 70, 3, 279--351.

[35]

Renyi, A., and Sulanke, R. 1963. Uber die convexe hulle von is zufallig gewahlten punkten, I. Z. Whar. 2, 75--84.

[36]

Renyi, A., and Sulanke, R. 1964. Uber die convexe hulle von is zufallig gewahlten punkten, II. Z. Whar. 3, 138--148.

[37]

Santalo, L. A. 1976. Integral Geometry and Geometric Probability. Encyclopedia of Mathematics and its Applications. Addison-Wesley, Reading, Mass.

[38]

Santha, M., and Vazirani, U. 1986. Generating quasi-random sequences from semi-random sources. J. Comput. System Sciences 33, 75--87.

[39]

Smale, S. 1982. The problem of the average speed of the simplex method. In Proceedings of the 11th International Symposium on Mathematical Programming. 530--539.

[40]

Smale, S. 1983. On the average number of steps in the simplex method of linear programming. Math. Prog. 27, 241--262.

[41]

Todd, M. 1986. Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems. Math. Prog. 35, 173--192.

[42]

Todd, M. J. 1991. Probabilistic models for linear programming. Math. Oper. Res. 16, 4, 671--693.

[43]

Todd, M. J., Tunçel, L., and Ye, Y. 2001. Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems. Math. Program., Ser. A 90, 59--69.

[44]

Turner, J. S. 1986. On the probable performance of a heuristic for bandwidth minimization. SIAM J. Comput. 15, 2, 561--580.

[45]

Vavasis, S. A., and Ye, Y. 1996. A primal-dual interior-point method whose running time depends only on the constraint matrix. Math. Program. 74, 79--120.

Cited By

Ameer WSohag KZhan QShah SYongjia Z(2025)Do financial development and institutional quality impede or stimulate the shadow economy? A comparative analysis of developed and developing countriesHumanities and Social Sciences Communications10.1057/s41599-024-04347-w12:1Online publication date: 4-Jan-2025
https://doi.org/10.1057/s41599-024-04347-w
Rohwedder LSafari AVredeveld T(2025)Smoothed analysis of the k-swap neighborhood for makespan schedulingOperations Research Letters10.1016/j.orl.2025.10724459(107244)Online publication date: Mar-2025
https://doi.org/10.1016/j.orl.2025.107244
Mahmoud NVirro IZaman ALillerand TChan WLiivapuu ORoy KOlt J(2024)Robust Object Detection Under Smooth Perturbations in Precision AgricultureAgriEngineering10.3390/agriengineering60402616:4(4570-4584)Online publication date: 29-Nov-2024
https://doi.org/10.3390/agriengineering6040261
Show More Cited By

Index Terms

Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
        Linear programming
    2. Numerical analysis
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Continuous optimization
        Linear programming

Recommendations

A friendly smoothed analysis of the simplex method
STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

Explaining the excellent practical performance of the simplex method for linear programming has been a major topic of research for over 50 years. One of the most successful frameworks for understanding the simplex method was given by Spielman and Teng (...
Smoothed analysis of dynamic networks

In this paper, we generalize the technique of smoothed analysis to apply to distributed algorithms in dynamic networks in which the network graph can change from round to round. Whereas standard smoothed analysis studies the impact of small random ...
Solving polynomial equations in smoothed polynomial time and a near solution to smale's 17th problem
STOC '10: Proceedings of the forty-second ACM symposium on Theory of computing

The 17th of the problems proposed by Steve Smale for the 21st century asks for the existence of a deterministic algorithm computing an approximate solution of a system of n complex polynomials in $n$ unknowns in time polynomial, on the average, in the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 51, Issue 3

May 2004

153 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/990308

Issue’s Table of Contents

Copyright © 2004 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 2004

Published in JACM Volume 51, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

473
Total Citations
View Citations
5,004
Total Downloads

Downloads (Last 12 months)188
Downloads (Last 6 weeks)20

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ameer WSohag KZhan QShah SYongjia Z(2025)Do financial development and institutional quality impede or stimulate the shadow economy? A comparative analysis of developed and developing countriesHumanities and Social Sciences Communications10.1057/s41599-024-04347-w12:1Online publication date: 4-Jan-2025
https://doi.org/10.1057/s41599-024-04347-w
Rohwedder LSafari AVredeveld T(2025)Smoothed analysis of the k-swap neighborhood for makespan schedulingOperations Research Letters10.1016/j.orl.2025.10724459(107244)Online publication date: Mar-2025
https://doi.org/10.1016/j.orl.2025.107244
Mahmoud NVirro IZaman ALillerand TChan WLiivapuu ORoy KOlt J(2024)Robust Object Detection Under Smooth Perturbations in Precision AgricultureAgriEngineering10.3390/agriengineering60402616:4(4570-4584)Online publication date: 29-Nov-2024
https://doi.org/10.3390/agriengineering6040261
Baßler PHeinrich MKliesch M(2024)Time-optimal multi-qubit gates: Complexity, efficient heuristic and gate-time boundsQuantum10.22331/q-2024-03-13-12798(1279)Online publication date: 13-Mar-2024
https://doi.org/10.22331/q-2024-03-13-1279
Xu XDing HWooldridge MDy JNatarajan S(2024)A novel skip orthogonal list for dynamic optimal transport problemProceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v38i18.30073(20838-20846)Online publication date: 20-Feb-2024
https://dl.acm.org/doi/10.1609/aaai.v38i18.30073
Nannicini G(2024)Fast Quantum Subroutines for the Simplex MethodOperations Research10.1287/opre.2022.234172:2(763-780)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1287/opre.2022.2341
Díaz AMorris PPerarnau GSerra O(2024)Speeding up random walk mixing by starting from a uniform vertexElectronic Journal of Probability10.1214/24-EJP109129:noneOnline publication date: 1-Jan-2024
https://doi.org/10.1214/24-EJP1091
Sayeh WAl-Qadi I(2024)Optimization of Network Pavement Life-Cycle Cost: A Piecewise Linearized ApproachTransportation Research Record: Journal of the Transportation Research Board10.1177/036119812412423702678:11(779-790)Online publication date: 16-May-2024
https://doi.org/10.1177/03611981241242370
Giannakopoulos YKleinberg RSaban DBergemann D(2024)A Smoothed FPTAS for Equilibria in Congestion GamesProceedings of the 25th ACM Conference on Economics and Computation10.1145/3670865.3673615(401-413)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3670865.3673615
Dinitz MFineman JGilbert SNewport C(2024)Smoothed Analysis of Information Spreading in Dynamic NetworksJournal of the ACM10.1145/366183171:3(1-24)Online publication date: 11-Jun-2024
https://dl.acm.org/doi/10.1145/3661831
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents