Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time Export

@misc{citeulike:1087293, abstract = {We introduce the smoothed analysis of algorithms, which is a hybrid of the worst-case and average-case analysis of algorithms. In smoothed analysis, we measure the maximum over inputs of the expected performance of an algorithm under small random perturbations of that input. We measure this performance in terms of both the input size and the magnitude of the perturbations. We show that the simplex algorithm has polynomial smoothed complexity.}, archivePrefix = {arXiv}, author = {Spielman, Daniel A. and Teng, Shang-Hua}, citeulike-article-id = {1087293}, citeulike-linkout-0 = {http://arxiv.org/abs/cs.DS/0111050}, citeulike-linkout-1 = {http://arxiv.org/pdf/cs.DS/0111050}, day = {9}, eprint = {cs.DS/0111050}, keywords = {algorithm, pad, simplex, smoothedanalysis}, month = {Oct}, posted-at = {2007-02-04 16:46:12}, priority = {2}, title = {Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time}, url = {http://arxiv.org/abs/cs.DS/0111050}, year = {2003} }

TY - ELEC ID - citeulike:1087293 L3 - citeulike-article-id:1087293 N2 - We introduce the smoothed analysis of algorithms, which is a hybrid of the worst-case and average-case analysis of algorithms. In smoothed analysis, we measure the maximum over inputs of the expected performance of an algorithm under small random perturbations of that input. We measure this performance in terms of both the input size and the magnitude of the perturbations. We show that the simplex algorithm has polynomial smoothed complexity. TI - Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time KW - algorithm KW - pad KW - simplex KW - smoothedanalysis AU - Spielman, Daniel AU - Teng, Shang-Hua PY - 2003/Oct/09/ UR - http://arxiv.org/abs/cs.DS/0111050 ER -