在算法分析领域，缩小理论与实践之间的差距一直是一个长期目标。为进一步推动我们对算法实际工作原理的理解，本文提出了一种新的算法分析框架，称为“以书本为依据分析”。与早期框架不同，“以书本为依据分析”不仅建模算法的输入数据，还同时建模算法本身。该框架的结果旨在与算法实际行为的既定知识相对应，基于实现观察、输入建模最佳实践以及实用基准实例的测量。
我们将此框架应用于单纯形法，这是一种因其在实践中的优秀表现而备受青睐，但在最坏情况下却以高运行时间而闻名的算法。单纯形法同样展示了最先进的平滑分析框架（Spielman 和 Teng，STOC'01）。我们解释了我们的框架如何克服平滑分析的若干弱点，并证明在输入缩放假设、可行性容忍度和单纯形法实现中使用的其他设计原则下，单纯形法确实达到了多项式运行时间。
博主点评： 本文提出的“以书本为依据分析”框架为算法分析提供了新的视角，尤其是在实际应用中的表现评估上，弥补了传统理论分析的不足。单纯形法的多项式时间复杂度的证明将为其在现实世界中的广泛应用提供理论支持，值得关注。