Smoothed Analysis Homepage

Research Papers on Smoothed Analysis

• Smoothed Analysis of Integer Programming (IPCO 2005, to appear in Mathematical Programming)
  By Heiko Röglin and Berthold Vöcking

• Smoothed Analysis of Binary Search Trees (ISAAC 2005)
  By Bodo Manthey and Rüdiger Reischuk

• Decision Making Based on Approximate and Smoothed Pareto Curves (ISAAC 2005)
  By Heiner Ackermann, Alantha Newman, Heiko Röglin, and Berthold Vöcking

• Beyond Hirsch Conjecture: walks on random polytopes and smoothed complexity of the simplex method (FOCS 2006)
  Roman Vershynin

• Worst-case and Smoothed Analyses of the ICP Algorithm, With an Application to the k-means Method. (FOCS 2006)
  By David Arthur and Sergei Vassilvitskii.

• Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP (ECCC TR06-092)
  By Matthias Englert, Heiko Röglin and Berthold Vöcking

• General formulas for the smoothed analysis of condition numbers (C. R. Acad. Sci. Paris, Ser. I 343, pp.145-150 (2006))
  By P. Bürgisser, F. Cucker and M. Lotz.

• Smoothed analysis of complex conic condition numbers (Journal de Mathématiques Pures et Appliquées, to appear)
  By P. Bürgisser, F. Cucker and M. Lotz.

• Smoothed Analysis of Algorithms: Why The Simplex Algorithm Usually Takes Polynomial Time,
  by Shang-Hua Teng, and Daniel A. Spielman

• Smoothed Analysis of the Perceptron Algorithm
  by Avrim Blum, and John Dunagan
  [Commentary on this result]

• Smoothed Analysis of the Renegar's Condition Number for Linear Programming
  by John Dunagan, Daniel A. Spielman , and Shang-Hua Teng

• Smoothed Analysis of Termination of Linear Programming Algorithms (Math Prog. B, Vol 97)
  by Daniel A. Spielman , and Shang-Hua Teng

• Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
  by Arvind Sankar, Shang-Hua Teng, and Daniel A. Spielman

• Smoothed Analysis of Three Combinatorial Problems (MFCS '03)
  by Cyril Banderier, Rene Beier , and Kurt Mehlhorn
  [Commentary on this result]

• Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm (FOCS 2003)
  By L. Becchetti, S. Leonardi, A. Marchetti-Spaccamela, G. Schäfer, and T. Vredeveld.

• Smoothed motion complexity (Proc. 11th European Symposium on Algorithms (ESA), 2003)
  By V. Damerov, F. Meyer auf der Heide, H. Raecke, C. Scheideler, and C. Sohler.

• Smoothed Number of Extreme Points under Uniform Noise. (20th European Workshop on Computational Geometry, 2004)
  by Valentina Damerow and Christian Sohler.

• Random walks on a randomly perturbed digraph
  by A Frieze and A. Flaxman.

• Typical Properties of Winners and Losers in Discrete Optimization (STOC 2004)
  by Rene Beier and Berthold Voecking.

• Random knapsack in expected polynomial time(STOC 2003)
  by Rene Beier and Berthold Voecking.

• Smoothed Analysis of Gaussian Elimination (Thesis, MIT 2004, paper to follow)
  by Arvind Sankar.

Surveys on Smoothed Analysis

• Smoothed Analysis of Algorithms: talk presented at ICM 2002.
  by Shang-Hua Teng, and Daniel A. Spielman

• Smoothed Analysis: Motivation and Discrete Models.
  by Shang-Hua Teng, and Daniel A. Spielman

• Coloring Random and Semi-Random k-Colorable Graphs.
  by Avrim Blum, and Joel Spencer
  Journal of Algorithms 19:204--234, 1995.

• "Improved performance guarantees for bandwidth minimization heuristics"
  by Uri Feige and Robert Krauthgamer
  

• "Heuristics for Semirandom Graph Problems"
  by Uri Feige and Joe Kilian.
  To appear in Journal of Computer and System Sciences.