[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: Thu, 14 Feb 2008 12:48:29 -0600 (CST)

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

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

reply via email to

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