如何确定单纯形时间复杂度（即最大流量） [英] How to determine simplex time complexity (ie Max flow)

问题描述

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

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

谢谢您的时间。

解决方案

平均情况下的复杂度很难分析，并且取决于线性程序的分布。我相信在某些常见分布下，它被认为是多项式时间。我目前找不到该论文。

编辑：是的，这是来源：

Nocedal，J。和Wright，SJ数值优化。纽约：施普林格出版社，1999年。

Forsgren，A .； Gill，P. E .;和Wright，M. H.非线性优化的内部方法。 SIAM Rev. 44，525-597，2002年。您可以在大学图书馆中找到任何一个。

Simplex algorithm is said to have exponential worst case time complexity. Yet it is still often used in practice. How can you determine the average time complexity for a certain problem (being solved with simplex).

For example, what is the average time complexity of the maximum flow problem being solved with simplex algorithm. (Wiki has time complexity for all other algorithms)

Thank you for your time.

解决方案

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.

这篇关于如何确定单纯形时间复杂度（即最大流量）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！