Re: [Help-glpk] GLPK complexity and scalability

[Andrew Makhorin]

>> LP is polynomial, but so far as I know,
>> no known simplex algorithm is polynomial.
>> 

> See
> Jonathan A. Kelner, Daniel A. Spielman
> "A Randomized Polynomial-Time Simplex Algorithm for Linear Programming", 
> 2005

> http://people.csail.mit.edu/kelner/PDFs/KelnerSpielmanSimplex.pdf

> In this article the authors claim to have found a Simplex algorithm with
> expected polynomial time.

There is the classical example by Klee and Minty, which shows that the
simplex method has exponential complexity. See, for example:

http://glossary.computing.society.informs.org/notes/Klee-Minty.pdf