Smoothed analysis: an attempt to explain the behavior of algorithms in practice

ABSTRACT

This Gödel Prize-winning work traces the steps toward modeling real data.

REFERENCES

• 1: Adler, I. The expected number of pivots needed to solve parametric linear programs and the efficiency of the self-dual simplex method. Technical report, University of California at Berkeley (May 1983).
• 2: Andoni, A. and Krauthgamer, R. The smoothed complexity of edit distance. In Proceedings of ICALP, volume 5125 of Lecture Notes in Computer Science (Springer, 2008) 357--369.
• 3: Arthur, D. and Vassilvitskii, S. How slow is the k-means method? In SOCG '06, the 22nd Annual ACM Symposium on Computational Geometry (2006) 144--153.
• 4: Arthur, D. and Vassilvitskii, S. Worst-case and smoothed analysis of the ICP algorithm, with an application to the k-means method. In FOCS '06, the 47th Annual IEEE Symposium on Foundations of Computer Science (2006) 153--164.
• 5: Becchetti, L., Leonardi, S., Marchetti-Spaccamela, A., Schfer, G., and Vredeveld, T. Average-case and smoothed competitive analysis of the multilevel feedback algorithm. Math. Oper. Res. 31, 1 (2006), 85--108.
• 6: Beier, R. and Vöcking, B. Typical properties of winners and losers in discrete optimization. In STOC '04: the 36th Annual ACM Symposium on Theory of Computing (2004), 343--352.
• 7: Blum, A. and Dunagan, J. Smoothed analysis of the perceptron algorithm for linear programming. In SODA '02 (2002), 905--914.
• 8: Blum, A. and Spencer, J. Coloring random and semi-random k-colorable graphs. J. Algorithms 19, 2 (1995), 204--234.
• 9: Bohman, T., Frieze, A. and Martin, R. How many random edges make a dense graph hamiltonian? Random Struct. Algorithms 22, 1 (2003), 33--42.
• 10: Bürgisser, P., Cucker, F., and Lotz, M. Smoothed analysis of complex conic condition numbers. J. de Mathématiques Pures Appliqués 86 4 (2006), 293--309.
• 11: Damerow, V., Meyer auf der Heide, F., Räcke, H., Scheideler, C., and Sohler, C. Smoothed motion complexity. In Proceedings of the 11th Annual European Symposium on Algorithms (2003), 161--171.
• 12: Dantzig, G.B. Maximization of linear function of variables subject to linear inequalities. Activity Analysis of Production and Allocation. T.C. Koopmans, Ed. 1951, 339--347.
• 13: Dunagan, J., Spielman, D.A., and Teng, S.-H. Smoothed analysis of condition numbers and complexity implications for linear programming. Mathematical Programming, Series A, 2009. To appear. Preliminary version available at http://arxiv.org/abs/cs/0302011v2.
• 14: Edelman, A. Eigenvalue roulette and random test matrices. Linear Algebra for Large Scale and Real-Time Applications. Marc S. Moonen, Gene H. Golub, and Bart L. R. De Moor, eds. NATO ASI Series, 1992, 365--368.
• 15: Englert, M., Röglin, H., and Vöcking, B. Worst case and probabilistic analysis of the 2-opt algorithm for the TSP: extended abstract. In SODA '07: The 18th Annual ACM-SIAM Symposium on Discrete Algorithms (2007), 1295--1304.
• 16: Feige, U. Refuting smoothed 3CNF formulas. In The 48th Annual IEEE Symposium on Foundations of Computer Science (2007), 407--417.
• 17: Flaxman, A. and Frieze, A.M. The diameter of randomly perturbed digraphs and some applications. In APPROX-RANDOM (2004), 345--356.
• 18: Gass, S. and Saaty, T. The computational algorithm for the parametric objective function. Naval Res. Logist. Quart. 2, (1955), 39--45.
• 19: Haimovich, M. The simplex algorithm is very good!: On the expected number of pivot steps and related properties of random linear programs. Technical report, Columbia University (April 1983).
• 20: Huang, L.-S. and Teng, S.-H. On the approximation and smoothed complexity of Leontief market equilibria. In Frontiers of Algorithms Workshop (2007), 96--107.
• 21: Kalai, A. and Teng, S.-H. Decision trees are PAC - learnable from most product distributions: a smoothed analysis. ArXiv e-prints (December 2008).
• 22: Karger, D. and Onak, K. Polynomial approximation schemes for smoothed and random instances of multidimensional packing problems. In SODA '07: the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (2007), 1207--1216.
• 23: Kelner, J.A. and Nikolova, E. On the hardness and smoothed complexity of quasi-concave minimization. In The 48th Annual IEEE Symposium on Foundations of Computer Science (2007), 472--482.
• 24: Kelner, J.A. and Spielman, D.A. A randomized polynomial-time simplex algorithm for linear programming. In The 38th Annual ACM Symposium on Theory of Computing (2006), 51--60.
• 25: Klee, V. and Minty, G.J. How good is the simplex algorithm? Inequalities -- III. O. Shisha, ed. Academic Press, 1972, 159--175.
• 26: Krivelevich, M., Sudakov, B. and Tetali, P. On smoothed analysis in dense graphs and formulas. Random Struct. Algorithms 29 (2005), 180--193.
• 27: Ma, B. Why greed works for shortest common superstring problem. In CPM '08: Proceedings of the 19th Annual Symposium on Combinatorial Pattern Matching (2008), 244--254.
• 28: Manthey, B. and Röglin, H. Improved smoothed analysis of the k-means method. In SODA '09 (2009).
• 29: Mehlhorn, K. and Näher, S. The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press, New York, 1999.
• 30: Mitzenmacher, M. and Vadhan, S. Why simple hash functions work: exploiting the entropy in a data stream. In SODA '08: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (2008), 746--755.
• 31: Röglin, H. and Vöcking, B. Smoothed analysis of integer programming. Proceedings of the 11th International Conference on Integer Programming and Combinatorial Optimization. M. Junger and V. Kaibel, eds. Volume 3509 of Lecture Notes in Computer Science, Springer, 2005, 276--290.
• 32: Rudelson, M. and Vershynin, R. The littlewood-offord problem and invertibility of random matrices. Adv. Math. 218, (June 2008), 600--633.
• 33: Sankar, A. Smoothed analysis of Gaussian elimination. Ph.D. Thesis, MIT, 2004.
• 34: Sankar, A., Spielman, D.A., and Teng, S.-H. Smoothed analysis of the condition numbers and growth factors of matrices. SIAM J. Matrix Anal. Appl. 28, 2 (2006), 446--476.
• 35: Spielman, D.A. and Teng, S.-H. Smoothed analysis of algorithms. In Proceedings of the International Congress of Mathematicians (2002), 597--606.
• 36: Spielman, D.A. and Teng, S.-H. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM 51, 3 (20040, 385--463.
• 37: Teng, S.-H. Algorithm design and analysis with perburbations. In Fourth International Congress of Chinese Mathematicans (2007).
• 38: Vershynin, R. Beyond Hirsch conjecture: Walks on random polytopes and smoothed complexity of the simplex method. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (2006), 133--142.
• 39: Vu, V.H. and Tao, T. The condition number of a randomly perturbed matrix. In STOC '07: the 39th Annual ACM Symposium on Theory of Computing (2007), 248--255.
• 40: Wschebor, M. Smoothed analysis of κ(a). J. Complexity 20, 1 (February 2004), 97--107.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics