Re: [Help-glpk] GLPK complexity and scalability

[Michael Hennebry]

On Wed, 13 Feb 2008, glpk xypron wrote:

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

Expected polynomial time is not the same as polynomial time.
Of course, an algorithm doesn't necessarily
have to be polynomial time to be useful.

-- 
Michael   address@hidden
"Those parts of the system that you can hit with a hammer (not advised)
are called Hardware;  those program instructions that you can only
curse at are called Software."