Geek Answers Handbook

How to determine the time complexity of a simplex (i.e. maximum flow)

The Simplex algorithm is said to have exponentially worse temporal complexity. However, it is still often used in practice. How can you determine the average time complexity for a specific problem (solved using a simplex).

For example, what is the average time complexity of the maximum flow problem solved by the simplex algorithm. (The wiki has a temporary complexity for all other algorithms)

Thank you for your time.

+8
algorithm big-o time-complexity simplex
source share
2 answers

The average complexity of the case is quite difficult to analyze, and it depends on the distribution of your linear program. I believe that it was designed as polynomial time within some common distributions. Currently I can not find the article.

EDIT : Yes, here are the sources:

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

Forsgren, A .; Gill, PE; and Wright, M. H. "Internal Methods of Nonlinear Optimization." SIAM Rev. 44, 525-597, 2002.

I read it in the first book and, apparently, it was proved in a separate article (Forsgren). You can find either in the university library.

+6
source share

If it's still interesting. The complexity of the time of a simplex is O ((n + m) * n).

n is the number of variables.

m are the limitations of the inequality.

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

But this upper bound is exponential in n.

+1
source share

More articles:


All Articles