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