[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] GLPK complexity and scalability

From: Andrew Makhorin
Subject: Re: [Help-glpk] GLPK complexity and scalability
Date: Thu, 14 Feb 2008 19:58:57 +0300

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

reply via email to

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