How to determine simplex time complexity (ie Max f

问题:

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.

回答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.

回答2:

If it is still interesting. Time complexity of simplex is O((n+m)*n).

n - number of variables.

m - inequality constraints.

Why? Because the number of iterations could be no more than n + m in case of n which is an upper bound on the numbers of vertices .

But this upper bound is exponential in n.