Smoothed Analysis of Algorithms and Heuristics
Smoothed Analysis of Algorithms and Heuristics
复制标题
算法和启发式的平滑分析
DOI：
10.1007/11533719_3
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
S. Teng
中科院分区：
文献类型：
--
作者：
S. Teng
长期以来，理论家们一直受到科学家和工程师们所熟知的在实践中运行良好的卓越算法和算法学的挑战，但其理论分析一直是负面的或不令人信服的。问题的根源在于算法通常以两种方式之一进行分析：最坏情况分析或平均情况分析。前者可能会不恰当地暗示算法的性能较差，而后者可能无法令人信服，因为它考虑的随机输入可能与实践中遇到的输入不相似。
我们引入平滑分析来帮助解释这些算法和算法的成功。平滑分析是最坏情况和平均情况分析的混合，继承了两者的优点。算法的平滑复杂度是在输入的轻微随机扰动下，算法的预期运行时间在其输入上的最大值，作为输入长度和扰动幅度的函数测量。如果一个算法具有低平滑复杂度，那么它应该在每个输入邻域中的大多数输入上表现良好。
在这次演讲中，我们将解释平滑分析如何帮助解释几个具有实际重要性的算法的出色观察行为。我们将综述光滑分析在单纯形法、高斯消去法、内点法以及其他一些优化算法和数学中的应用进展。特别是，我们证明了单纯形算法具有多项式平滑的复杂性。单纯形算法是一个经典的例子，它在实践中表现良好，但在最坏的情况下需要指数时间。
这是与麻省理工学院的丹尼尔斯皮尔曼、微软研究院的约翰杜纳根和麻省理工学院的阿文德桑卡尔的联合工作。
The theorists have long been challenged by the existence of remarkable algorithms and heuristics that are known by scientists and engineers to work well in practice, but whose theoretical analyses have been are negative or unconvincing. The root of the problem is that algorithms are usually analyzed in one of two ways: by worst-case or average-case analysis. The former can improperly suggest that an algorithm will perform poorly, while the latter can be unconvincing because the random inputs it considers may fail to resemble those encountered in practice.
We introduce smoothed analysis to help explain the success of some of these algorithms and heuristics. Smoothed analysis is a hybrid of worst-case and average-case analyses that inherits advantages of both. The smoothed complexity of an algorithm is the maximum over its inputs of the expected running time of the algorithm under slight random perturbations of that input, measured as a function of both the input length and the magnitude of the perturbations. If an algorithm has low smoothed complexity, then it should perform well on most inputs in every neighborhood of inputs.
In this talk, we will explain how smoothed analysis can help explain the excellent observed behavior of several algorithms of practical importance. We will survey progresses on applying smoothed analysis to the simplex method, Gaussian elimination, interior point methods, and some other optimization algorithms and heuristics. In particular, we show that the simplex algorithm has polynomial smoothed complexity. The simplex algorithm is the classic example of an algorithm that performs well in practice but takes exponential time in the worst case.
This is joint work with Daniel Spielman of MIT, and with John Dunagan (Microsoft Research) and Arvind Sankar (MIT).