Smoothed Analysis of Algorithms. Spielman, D. A and Teng, S. ICM, 2002.
abstract   bibtex   
Spielman and Teng [STOC '01] introduced the smoothed analysis of al-gorithms to provide a framework in which one could explain the success in practice of algorithms and heuristics that could not be understood through the traditional worst-case and average-case analyses. In this talk, we survey some of the smoothed analyses that have been performed.
@article{Spielman2002,
abstract = {Spielman and Teng [STOC '01] introduced the smoothed analysis of al-gorithms to provide a framework in which one could explain the success in practice of algorithms and heuristics that could not be understood through the traditional worst-case and average-case analyses. In this talk, we survey some of the smoothed analyses that have been performed.},
archivePrefix = {arXiv},
arxivId = {arXiv:math/0212413v1},
author = {Spielman, Daniel A and Teng, Shang-Hua},
eprint = {0212413v1},
file = {:home/jax/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Spielman, Teng - 2002 - Smoothed Analysis of Algorithms.pdf:pdf},
journal = {ICM},
keywords = {2000 Mathematics Subject Classification,65Y20,68Q17,68Q25,90C05 Keywords and Phrases,Condition number,Interior point method,Perceptron algorithm,Simplex method,Smoothed analysis},
pages = {597--606},
primaryClass = {arXiv:math},
title = {{Smoothed Analysis of Algorithms}},
year = {2002}
}
Downloads: 0