推荐npalli · 2022-06
“The two authors won the Godel prize in 2008 for this work.”
提到两位作者因这项工作获得 2008 年哥德尔奖
提出平滑分析,解释单纯形法为何在实践中通常很快
引入平滑分析,它介于最坏情况分析与平均情况分析之间:度量在输入受到小幅随机扰动后,算法在最坏输入上的期望表现,并同时按输入规模和扰动幅度来衡量。论文证明单纯形算法具有多项式的平滑复杂度。
评论者用它解释单纯形法理论上最坏情况很差、实践中却很快的原因,并提到两位作者因此工作获得 2008 年哥德尔奖。
“The two authors won the Godel prize in 2008 for this work.”
“there are some interesting results that extend beyond that (see Smoothed Analysis of Algorithms)”
“Spielman solved that problem in 2001 and showed that even very small perturbations from a contrived worst-case input have good performance:”
“This is an interesting fact. Apparently this is the source?”