From: borchers@rainbow.nmt.edu (Brian Borchers) Subject: Re: Karmarkar's method Date: Sun, 4 Feb 2001 20:55:24 +0000 (UTC) Newsgroups: sci.math.num-analysis,sci.op-research Summary: Interior point methods in linear programming Tim Chow wrote: >Doesn't the term "interior point method" include the ellipsoid method? This is a question of nomenclature, and it clearly depends on how you define "interior point method", but I personally wouldn't consider the ellipsoid algorithm to be an interior point method because it isn't similar in its details or in its performance to the other methods that we now call "interior point methods." Khachian's ellipsoid algorithm (1979) settled the issue of whether or not LP could be solved in polynomial time, and soon led to the important result of Groetschel, Lovasz, and Schrijver on the polynomial equivalence of separation and optimization (1981.) However, it was quickly discovered that this algorithm was of little computational use. Khachian's algorithm requires O(n^2 L) iterations (n is the number of variables, L is the size of the problem data in bits) while interior point methods typically require O(sqrt(n) L) iterations. I'm aware of some papers which showed connections between the ellipsoid algorithm and what are now called interior point methods, but the connection is (IMHO) tenuous. Looking through the contemporary books on my shelf that discuss interior point methods I find that the ellipsoid algorithm is seldom discussed in more than an historical footnote. One older book that contains a very readable discussion of the ellipsoid method is Chvatal's "Linear Programming." -- Brian Borchers borchers@nmt.edu Department of Mathematics http://www.nmt.edu/~borchers/ New Mexico Tech Phone: 505-835-5813 Socorro, NM 87801 FAX: 505-835-5366