Re: [Help-glpk] GLPK complexity and scalability

[Michael Hennebry]

On Thu, 14 Feb 2008, Andrew Makhorin 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.
>
> 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

These are not in conflict.
The Klee-Minty example was designed to be
exponential for a particular simplex algorithm.

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