| There have been quite a few publications of his algorithm in the
past several years. The one that I could put my hands on immediately
is: "Karmarkar's Linear Programming Algorithm," Interfaces (16)4
July-August 1986 pp. 75-90. The projective scaling (or interior
point) method is explained with examples.
That article (written by Hooker at CMU) references two of Karmarkar's
papers: "A new polynomial-time algorithm for linear programming,"
Proceedings of the 16th Annual ACM Symposium on the Theory of
Computing, pp. 302-311; and a paper by the same title which appeared
in Combinatorica, Vol 4, No. 4, pp 373-395.
In addition there is a special issue of Algorithmica that addresses
this topic. It came out some time in early 1987 I believe.
The algorithm has been tested and highly touted as a means for solution
to special cases of linear progamming. But you should note that
the algorithm has been patented (that's right the ALGORITHM is
PATENTED) and the only firm with rights to its use (other than AT&T,
Karmarkar's employer, is IBM). AT&T is threatening a researcher
in Arizona for implementing the interior point method with a law
suit if he proceeds with this research. This could get real
interesting!
Is anybody currently working on interior points methods?
Oh, I almost forgot. In Boston on April 3-5 at the Park Plaza Hotel in
Boston, the 3rd SIAM (Soc. of Indus. & Appl. Math.) Conference on
Optimization is taking place. Karmarker will be presenting two
minisymposia at that time -- one on Tuesday and one on Wednesday. (I am
presenting my work at that conference and would enjoy meeting other
employees interested in the same line of work.)
Tim
|
| This is interesting - Dr. Roy Marsten at U. of Arizona has applied
to Digital for funding of work porting Karmarkar's algorithms to a
VAX. We looked at his application and decided not to fund it
(not based on suspicions that it was a patent infringement as we
weren't aware until last week that Karmarkar's algorithm was patented).
Other articles you might want to look at are the research proposal
put forth by Roy Marsden (see the ERP notes conference), and
Adler, Karmarkar, Resende, Veiga - An Implementation of Karmarkar's
Algorithm for Linear Programming, UC Berkeley, ORC 86-8
|