algorithm - 如何确定单纯形时间复杂度(即Max flow)

Question

据说单纯形算法具有指数级的最坏情况时间复杂度。但它仍然经常在实践中使用。如何确定某个问题的平均时间复杂度(使用单纯形法解决)。

例如，用单纯形算法求解的最大流问题的平均时间复杂度是多少。 (Wiki 对所有其他算法都有时间复杂度)

感谢您的宝贵时间。

Answer 1

平均案例复杂度很难分析，它取决于线性程序的分布。我相信它在一些常见的分布下被计算为多项式时间。不过我目前找不到这篇论文。

编辑:是的，这里是来源:

Nocedal, J. 和 Wright, S. J. 数值优化。纽约:施普林格出版社，1999。

福斯格伦，A.；吉尔，P. E.；和 Wright, M. H. “非线性优化的内部方法”。 SIAM Rev. 44, 525-597, 2002.

我在第一本书中读到了它，显然它在另一篇论文 (Forsgren) 中得到了证明。您可以在大学图书馆找到。