Re: [Help-glpk] GLPK complexity and scalability

[glpk xypron]

-------- Original-Nachricht --------
> Datum: Thu, 14 Feb 2008 12:48:29 -0600 (CST)
> Von: Michael Hennebry <address@hidden>
> An: Andrew Makhorin <address@hidden>
> CC: glpk xypron <address@hidden>, address@hidden, address@hidden
> Betreff: Re: [Help-glpk] GLPK complexity and scalability

> 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
> >
> > > 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
> 
> These are not in conflict.
> The Klee-Minty example was designed to be
> exponential for a particular simplex algorithm.
> 
> -- 
> Michael   address@hidden

Hello Micheal,

according to 
Randomized simplex algorithms on Klee-Minty cubes
Gartner, B.; Ziegler, G.M.
Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on
Volume , Issue , 20-22 Nov 1994 Page(s):502 - 510
http://www.inf.ethz.ch/personal/gaertner/texts/own_work/km_revised.pdf

Klee-Minty Cubes likes those in
http://glossary.computing.society.informs.org/notes/Klee-Minty.pdf

only help to prove non polynomial run time for deterministic pivot rules.

Best regards 

Xypron
-- 
Psssst! Schon vom neuen GMX MultiMessenger gehört?
Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger