algorithm - 如何确定单纯形时间复杂度（即最大流量）

Question

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

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

感谢您的时间。

Answer 1

The average case complexity is rather difficult to analyze and it depends on the distribution of your linear program. I believe that it was worked out to be polynomial time under some common distributions. I currently cannot find the paper though.

EDIT: Yes, here are the sources:

Nocedal, J. and Wright, S. J. Numerical Optimization. New York: Springer-Verlag, 1999.

Forsgren, A.; Gill, P. E.; and Wright, M. H. "Interior Methods for Nonlinear Optimization." SIAM Rev. 44, 525-597, 2002.

I read it in the first book and apparently it was proven in a separate paper (Forsgren). You could find either in a university library.

Answer 2

如果它仍然很有趣。单纯形的时间复杂度为 O((n+m)*n)。

n - 变量数。

m - 不等式约束。

为什么？因为在 n 是顶点数的上限的情况下，迭代次数不能超过 n + m。

但是这个上限是 n 的指数。