Smoothed analysis
Encyclopedia
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. In 2010 Spielman received the Nevanlinna Prize
for developing smoothed analysis. Spielman and Teng's JACM paper "Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time" was also one of the three winners of the 2009 Fulkerson Prize
sponsored jointly by the Mathematical Programming Society
(MPS) and the American Mathematical Society
(AMS).
Analysis of algorithms
To analyze an algorithm is to determine the amount of resources necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length...
. 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
Simplex algorithm
In mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming. The journal Computing in Science and Engineering listed it as one of the top 10 algorithms of the twentieth century....
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
Mathematical Programming
Mathematical Programming, established in 1971, and published by Springer Science+Business Media, is the official scientific journal of the Mathematical Optimization Society. It currently consists of two series: A and B. The "A" series contains general publications. The "B" series focuses on topical...
, numerical analysis
Numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis ....
, machine learning
Machine learning
Machine learning, a branch of artificial intelligence, is a scientific discipline concerned with the design and development of algorithms that allow computers to evolve behaviors based on empirical data, such as from sensor data or databases...
, and data mining
Data mining
Data mining , a relatively young and interdisciplinary field of computer science is the process of discovering new patterns from large data sets involving methods at the intersection of artificial intelligence, machine learning, statistics and database systems...
.
ACM
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
and the European Association for Theoretical Computer Science
EATCS
The European Association for Theoretical Computer Science is an international organization with a European focus, founded in 1972...
awarded the 2008 Gödel Prize
Gödel Prize
The Gödel Prize is a prize for outstanding papers in theoretical computer science, named after Kurt Gödel and awarded jointly by the European Association for Theoretical Computer Science and the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory .The...
to Daniel Spielman
Daniel Spielman
Daniel Alan Spielman is professor of Applied Mathematics and Computer Science at Yale University ....
and Shanghua Teng
Shanghua Teng
Shang-Hua Teng is the chairman of the Computer Science Department at the Viterbi School of Engineering of the University of Southern California. In 2008 he was awarded the Gödel Prize for his joint work on smoothed analysis of algorithms with Daniel Spielman...
for developing smoothed analysis. In 2010 Spielman received the Nevanlinna Prize
Nevanlinna Prize
The Rolf Nevanlinna Prize is awarded once every 4 years at the International Congress of Mathematicians, for outstanding contributions in Mathematical Aspects of Information Sciences including:...
for developing smoothed analysis. Spielman and Teng's JACM paper "Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time" was also one of the three winners of the 2009 Fulkerson Prize
Fulkerson Prize
The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Programming Society and the American Mathematical Society . Up to three awards of $1500 each are presented at each International Symposium of the MPS...
sponsored jointly by the Mathematical Programming Society
Mathematical Programming Society
Known as the Mathematical Programming Society until 2010, the Mathematical Optimization Society is an international association of researchers active in optimization...
(MPS) and the American Mathematical Society
American Mathematical Society
The American Mathematical Society is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, which it does with various publications and conferences as well as annual monetary awards and prizes to mathematicians.The society is one of the...
(AMS).