期刊
JOURNAL OF THE ACM
卷 51, 期 3, 页码 385-463出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/990308.990310
关键词
algorithms; theory; simplex method; smoothed analysis; complexity; perturbation
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据