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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]