Smoothed Analysis (Motivation and Discrete Models)
Smoothed Analysis (Motivation and Discrete Models)
复制标题
平滑分析（动机和离散模型）
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
S. Teng
中科院分区：
文献类型：
--
作者：
D. Spielman;S. Teng
在平滑分析中，假设算法的输入受到少量随机噪声的影响，则可以衡量算法的复杂性。在早期的工作(Spielman和Teng，2001)中，我们引入了这种分析来解释单纯形算法的良好实践行为。在本文中，我们为算法的平滑分析提供了进一步的动机，并建立了适合于分析离散算法行为的噪声模型。然后，我们考虑在这些模型中测试一些简单的图属性的平滑复杂性。
In smoothed analysis, one measures the complexity of algorithms assuming that their inputs are subject to small amounts of random noise. In an earlier work (Spielman and Teng, 2001), we introduced this analysis to explain the good practical behavior of the simplex algorithm. In this paper, we provide further motivation for the smoothed analysis of algorithms, and develop models of noise suitable for analyzing the behavior of discrete algorithms. We then consider the smoothed complexities of testing some simple graph properties in these models.