[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] GLPK complexity and scalability
From: |
Michael Hennebry |
Subject: |
Re: [Help-glpk] GLPK complexity and scalability |
Date: |
Wed, 13 Feb 2008 08:46:59 -0600 (CST) |
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."