Smoothed Analysis Homepage
[Introduction]
[Papers]
[Surveys]
[FAQ]
[Acknowledgement]
Research Papers on Smoothed Analysis
We are aware of the following 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

Worstcase and Smoothed Analyses of the ICP Algorithm, With an Application to
the kmeans Method.
(FOCS 2006)
By David Arthur and Sergei Vassilvitskii.
 Worst Case and Probabilistic Analysis of the 2Opt Algorithm for
the TSP (ECCC TR06092)
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.145150 (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
ShangHua 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
ShangHua Teng

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

Smoothed Analysis of the Condition Numbers
and Growth Factors of Matrices
by
Arvind Sankar,
ShangHua 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 MultiLevel
Feedback
Algorithm
(FOCS 2003)
By
L. Becchetti, S. Leonardi, A. MarchettiSpaccamela, 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
A precursor to smoothed complexity may be found in the
following papers inspired by Santha and Vazirani's
semirandom source model.
The papers are concerned with discrete analogues of
smoothed analysis.
Last modified: Thu Jun 30 12:47:49 EDT 2005