**dgc@ucla-cs.UUCP** (12/16/84)

[] The Karmaker Algorithm appears in the "Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing" (1984), pp 302-311. It can be ordered from the ACM Order Department P.O. Box 64145 Baltimore, MD 21264 Its ACM order number is 508840 and its ISBN number is 0-89791-133-4. Cost to ACM members is $29.00 and to all others is $38.00. It is available in most research libraries which cover computer science or mathematics. There has been a great deal of media "hype" on this algorithm, somewhat similar to the hype which followed the Khatchian alogrithm 4 years ago, and which turned out to be highly exaggerated. The value of the Karmaker algorithm remains to be seen. For another viewpoint, here is a comment by Walter Murray of Stanford University. It was distributed to the Numerical Analysis Community by Gene Golub: "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 l-2 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." David G. Cantor ARPA: dgc@ucla-locus.arpa UUCP: ...!{ihnp4, randvax, sdcrdcf, ucbvax}!ucla-cs!dgc

**parker@psuvax1.UUCP (Bruce Parker)** (12/27/84)

> [] > > The Karmaker Algorithm appears in the "Proceedings of the Sixteenth > Annual ACM Symposium on Theory of Computing" (1984), pp 302-311. > It can be ordered from the > > ACM Order Department > P.O. Box 64145 > Baltimore, MD 21264 > > Its ACM order number is 508840 and its ISBN number is 0-89791-133-4. > Cost to ACM members is $29.00 and to all others is $38.00. It is > available in most research libraries which cover computer science or > mathematics. Or you can ask for a reprint of just the paper for only $0.75 (at least if I'm reading this footnote correctly). Its number is 0-89791-133-4/84/004/0302. -- Bruce Parker Computer Science Department (814) 863-1545 334 Whitmore Lab {allegra|ihnp4}!psuvax1!parker The Pennsylvania State University parker@penn-state (csnet) University Park, Pennsylvania 16802 parker@psuvax1 (bitnet)