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

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: Milton Abramowitz, Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables,, Dover Publications, Incorporated, 1974
• 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: Ilan Adler , Richard M. Karp , Ron Shamir, A simplex variant solving an m×d linear program in O(min(m2,d2)) expected number of pivot steps, Journal of Complexity, v.3 n.4, p.372-387, December 1, 1987 [doi>10.1016/0885-064X(87)90007-0]
• 4: Ilan Adler , Nimrod Megiddo, A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension, Journal of the ACM (JACM), v.32 n.4, p.871-895, Oct. 1985 [doi>10.1145/4221.4222]
• 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: Avrim Blum , Joel Spencer, Coloring random and semi-random k-colorable graphs, Journal of Algorithms, v.19 n.2, p.204-234, Sept. 1995 [doi>10.1006/jagm.1995.1034]
• 9: Borgwardt, K. H. 1977. Untersuchungen zur asymptotik der mittleren schrittzahl von simplexverfahren in der linearen optimierung. Ph.D. dissertation, Universitat Kaiserslautern.
• 10: Karl Heinz Borgwardt, A probabilistic analysis of the simplex method, Springer-Verlag New York, Inc., New York, NY, 1986
• 11: Tony F. Chan , Per Christian Hansen, Some applications of the rank revealing QR factorization, SIAM Journal on Scientific and Statistical Computing, v.13 n.3, p.727-741, May 1992 [doi>10.1137/0913043]
• 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: Uriel Feige , Joe Kilian, Heuristics for Finding Large Independent Sets, with Applications to Coloring Semi-random Graphs, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.674, November 08-11, 1998
• 16: Feige, U., and Krauthgamer, R. 1998. Improved performance guarantees for bandwidth minimization heuristics. http://www.cs.berkeley.edu/∼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: Gil Kalai, A subexponential randomized simplex algorithm (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.475-482, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129759]
• 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: N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
• 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: Nimrod Megiddo, Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm, Mathematical Programming: Series A and B, v.35 n.2, p.140-172, June 1986 [doi>10.1007/BF01580645]
• 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: James Renegar, Some perturbation theory for linear programming, Mathematical Programming: Series A and B, v.65 n.1, p.73-91, May 31, 1994 [doi>10.1007/BF01581690]
• 33: Renegar, J. 1995a. Incorporating condition measures into the complexity theory of linear programming. SIAM J. Optim. 5, 3, 506--524.
• 34: James Renegar, Linear programming, complexity theory and elementary functional analysis, Mathematical Programming: Series A and B, v.70 n.3, p.279-351, Nov. 20, 1995 [doi>10.1007/BF01585941]
• 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: Miklos Santha , Umesh V Vazirani, Generating quasi-random sequences from semi-random sources, Journal of Computer and System Sciences, v.33 n.1, p.75-87, Aug. 1986 [doi>10.1016/0022-0000(86)90044-9]
• 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: Micheal J Todd, Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems, Mathematical Programming: Series A and B, v.35 n.2, p.173-192, June 1986 [doi>10.1007/BF01580646]
• 42: Michael J. Todd, Probabilistic models for linear programming, Mathematics of Operations Research, v.16 n.4, p.671-693, Nov. 1991 [doi>10.1287/moor.16.4.671]
• 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: Jonathan S Turner, On the probable performance of Heuristics for bandwidth minimization, SIAM Journal on Computing, v.15 n.2, p.561-580, May 1986 [doi>10.1137/0215041]
• 45: Stephen A. Vavasis , Yinyu Ye, A primal-dual interior point method whose running time depends only on the constraint matrix, Mathematical Programming: Series A and B, v.74 n.1, p.79-120, July 31, 1996 [doi>10.1007/BF02592148]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

General Terms:
Algorithms, Theory

Keywords:
Simplex method, complexity, perturbation, smoothed analysis