Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time
Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time
复制标题
DOI：
10.1145/990308.990310
复制
发表时间：
2004-05-01
影响因子：
2.5
通讯作者：
Teng, SH
中科院分区：
文献类型：
--
作者：
Spielman, DA;Teng, SH
我们介绍了平滑分析的算法，它不断插值之间的最坏情况和平均情况的算法分析。在平滑分析中，我们测量在输入的小随机扰动下算法的预期性能的最大输入。我们衡量这方面的输入大小和扰动的幅度的性能。我们证明了单纯形算法在输入规模和高斯扰动的标准差上平滑了复杂性多项式。
We introduce the smoothed analysis of algorithms, which continuously interpolates between the worst-case and average-case analyses 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 smoothed complexity polynomial in the input size and the standard deviation of Gaussian perturbations.