From: David A Molnar <dmolnar@fas.harvard.edu>
Subject: Re: Karmarker's Method
Date: 9 May 2000 21:07:42 GMT
Newsgroups: sci.math
Summary: [missing]

Dave Rusin <rusin@vesuvius.math.niu.edu> wrote:

> That's a bit of an over-statement. Yes, it's true that practically speaking,
> algorithms based on the Simplex algorithm continue to be the best, so

Is it ? I was under the impression for some reason that interior point
methods still won under some situations. More to the point, I thought that
Karmarkar's algorithm actually did provide a practical improvement at the
time, unlike the ellipsoid method. I had thought that this practical
improvement spurred the development of simplex methods and simplex
implementations in a way that the polytime but impractical ellipsoid
method did not. 

> exponentially with the number of constraints. (The worst cases fool the
> algorithm -- basically a greedy algorithm -- into checking many of the
> vertices before finding the optimal one.) The interior point methods

Just a minor point - this depends on your choice of pivot rule for the
simplex method. There's a pivot rule due to Zadeh for which I do not know
of any pathological case which takes exponential time. 
This pivot rule is referred to in "Randomized Algorithms on
Klee-Minty Cubes" by Ga"rtner, Henk, and Ziegler : 

tech report version :
http://www.inf.fu-berlin.de/inst/pubs/tr-b-94-13.abstract.html

if you have Springer LINK : 
http://link.springer.de/link/service/journals/00493/bibs/8018003/80180349.htm

The idea seems to be "keep track of which variables you have used least,
and then pick from among those the one which most enhances the objective
function." Apparently there's a US$1000 prize for determining that this
pivot rule has a pathological/exptime example, or for proving that none
such exists. 

Unfortunately, the document describing this rule in detail seems to be a
Stanford U tech report from 1980, which I don't have at the moment. 

Thanks,
-David Molnar