Smoothed analysis

Smoothed analysis

Smoothed analysis is a way of measuring the complexity of an algorithm. It gives a more realistic analysis of the practical performance of the algorithm, such as its running time, than using worst-case or average-case scenarios.

For instance the simplex algorithm runs in exponential-time in the worst-case and yet in practice it is a very efficient algorithm. This was one of the main motivations for developing smoothed analysis.

Average-case analysis was first introduced to overcome the limitations of worst-case analysis, however the difficulty is saying what an average case is. The actual inputs and distribution of inputs may be different in practice from the assumptions made during the analysis.

Smoothed analysis is a hybrid of worst-case and average-case analyses that inherits advantages of both, by measuring the expected performance of algorithms under slight random perturbations of worst-case inputs. If the smoothed complexity of an algorithm is low, then it is unlikely that the algorithm will take long time to solve practical instances whose data are subject to slight noises and imprecisions.

Since its introduction in 2001, smoothed analysis has been used as a basis for considerable research, for problems ranging from mathematical programming, numerical analysis, machine learning, and data mining. ACM and the European Association for Theoretical Computer Science awarded the 2008 Gödel Prize to Daniel Spielman and Shanghua Teng for developing smoothed analysis.

References

* | year=2001 | chapter=Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time | pages=296–305.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Analysis of algorithms — To analyze an algorithm is to determine the amount of resources (such as time and storage) necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length. Usually the efficiency or running time of an algorithm is… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • Trix (technical analysis) — Trix (or TRIX) is a technical analysis oscillator developed in the 1980s by Jack Hutson, editor of Technical Analysis of Stocks and Commodities magazine. It shows the slope (ie. derivative) of a triple smoothed exponential moving average. The… …   Wikipedia

  • Technical analysis — Financial markets Public market Exchange Securities Bond market Fixed income Corporate bond Government bond Municipal bond …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Daniel Spielman — Residence U.S. Nationality …   Wikipedia

  • Daniel Spielman — Daniel Alan Spielman (* März 1970 in Philadelphia) ist ein US amerikanischer Mathematiker und Informatiker. Inhaltsverzeichnis 1 Berufliche Laufbahn 2 Auszeichnungen 3 Weblinks 4 …   Deutsch Wikipedia

  • Shang-Hua Teng — (* in Peking) ist ein chinesisch US amerikanischer Mathematiker und Informatiker. Teng, Sohn eines Professors für Bauingenieurwesen, studierte ab 1981 Elektrotechnik und Informatik an der Jiao Tong Universität in Shanghai (Bachelor Abschluss… …   Deutsch Wikipedia

  • Daniel Spielman — Naissance mars 1970 Domicile États Unis Nationalité …   Wikipédia en Français

  • Shanghua Teng — Infobox Scientist name = Shang Hua Teng image width = 150px caption = birth date = birth place = China residence = nationality = field = Computer Scientist work institution = Boston University alma mater = Shanghai Jiao Tong University University …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”