按年被提到
20012016 · 2 次2026
算法与数据结构›经典算法与数据结构·arXiv:cs/0111050 · cs.DS

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

算法的平滑分析:为什么单纯形法通常是多项式时间
Daniel A. Spielman, Shang-Hua Teng · 2001

提出平滑分析,解释单纯形法为何在实践中通常很快

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 6 人首次 2008-02-07 · 最近 2024-11-02
6不同的人
7活跃月份
7讨论串
61被引(OpenAlex)

引入平滑分析,它介于最坏情况分析与平均情况分析之间:度量在输入受到小幅随机扰动后,算法在最坏输入上的期望表现,并同时按输入规模和扰动幅度来衡量。论文证明单纯形算法具有多项式的平滑复杂度。

HN 为什么提它

评论者用它解释单纯形法理论上最坏情况很差、实践中却很快的原因,并提到两位作者因此工作获得 2008 年哥德尔奖。

奠基之作难度 5 / 5约 120 分钟经得起时间
读之前最好知道
1线性规划与单纯形法
2最坏情况与平均情况分析
3概率论与高维几何
4算法复杂度

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
推荐npalli · 2022-06

“The two authors won the Godel prize in 2008 for this work.”

提到两位作者因这项工作获得 2008 年哥德尔奖
The Simplex Solution: Why it works so well原评论 ↗
引用mzl · 2011-01

“there are some interesting results that extend beyond that (see Smoothed Analysis of Algorithms)”

指出平滑分析还有超出当前话题的有趣结果
The polynomial algorithm for 3-SAT problem (or P=NP)原评论 ↗
引用luu · 2016-06

“Spielman solved that problem in 2001 and showed that even very small perturbations from a contrived worst-case input have good performance:”

指出 Spielman 在 2001 年证明对最坏输入做微小扰动后性能很好
Linear Programming: How Does It Work?原评论 ↗
引用FooBarBizBazz · 2024-11

“This is an interesting fact. Apparently this is the source?”

猜测这就是扰动后单纯形法为多项式时间这一事实的来源
Suits, money laundering, and linear programming原评论 ↗
被提交为 story · 3 次