Conference rusure::math

	Does anyone know which (or what class of) problem are they talking
	about?  Is it the Traveling Salesman problem?

	- Paul

The problem is linear programming. An article appeared in Science
magazine recently but gave no details of the algorithm. Karnarkar
claims it performs much faster than simplex even on moderate sized
problems.

An improvement in linear programming problems was to be expected.  Five or six
years ago a Russian (?) showed that linear programming problems could be solved
in polynomial time (n^2, methinks), but the method had a very large 'constant',
so the Simplex algorithm was still preferred for most problems.  However, it was
expected the technique could be improved.  Or that a different algorithm could
be discovered, now that linear programming was known to admit asymtotically fast
solutions, and the Russian's result had prompted further research in the area.

The Russian Gilbert mentions is named Khachian.

A much better writeup on the algorithm appeared in the New York Times last
week.  This time, their reporter actually understood what was going on, or
faked it well.  (Their article on Khachian's algorithm claimed it would solve
the Traveling Salesman problem.)

All indications I've seen are that this new algorithm really is a breakthrough.
It is practical and significantly faster than the simplex method for large N.
The explanation I've seen of what is going on - VERY general - go something like
this:  Rather than explore the edges of the solution polytope, find the center
point, then go straight up until you hit a face (or edge).  From there, shift
back in to the center and repeat.  The difficult part in all this is setting
things up so that moving "up" from the "center" is actually moving you toward
the optimum.  This is done by applying a projective transformation at each
step before "returning to the midpoint".

Copies of the paper describing the algorithm are floating around; if I get hold
of one, I'll put some details here.  The thing to note is that it differs in
basic design both from the simplex method, which crawls around the edges of
the solution polytope, and Khachian's algorithm, which does a divide-and-con-
quer on the volume of the polytope using carefully constructed ellipsoids.

							-- Jerry

The new algorithm is due to Karmarkar.  The following note, sent to the CSNET
THEORY mailing list, tells you how to find out more about it:

	Date: 27 Nov 1984 17:19:38-EST (Tuesday)
	From: [email protected]
	To: @THEORY@WISC-RSCH>
	Subject: Karmarkar Algorithm

	The Karmarkar algorithm was presented at STOC (Symposium on Theory of
	Computing) on May 1, 1984 (STOC '84, p. 302) "A New Polynomial time
	Algorithm on Linear Programming".  The STOC proceedings are available
	from the ACM if your location doesn't have them.

							-- Jerry

Another comment from the Theory mailing list.  Judge it for yourself; I
too little - nothing, in fact - about approximation theory to know whether
what he has to say is real or sour grapes:

	Return-Path: <[email protected]>
	Date: Thu, 29 Nov 84 14:40:37 cst
	From: Walter Murray <[email protected]>
	Subject: Linear Progamming Algorithms.

	Some recent bboard messages have referred to linear programming. The
	algorithm by Karmarkar is almost identical with iterative reweighted
	least squares (IRLS). This latter algorithm is used to solve
	approximation problems other than in the l2 norm. It can be shown that
	the form of LP assumed by Karmarkar is equivalent to an l infinity
	approximation problem. If this problem is then solved by the IRLS
	algorithm the estimates of the solution generated are identical to
	those of the Karmarkar algorithm (assuming certain free choices in the
	definition of the algorithms). Perhaps it should be added that the
	algorithm is  not held in high regard in approximation circles. To
	solve a an l infinity problem it is usually transformed to an LP and
	solved using the simplex method.

							-- Jerry