Re: [Help-glpk] GLPK complexity and scalability

[glpk xypron]

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

Best regards

Xypron
-- 
Der GMX SmartSurfer hilft bis zu 70% Ihrer Onlinekosten zu sparen! 
Ideal für Modem und ISDN: http://www.gmx.net/de/go/smartsurfer