gtsc@dmcnh.UUCP (12/28/84)
kill -9 `pid(bug)` The following is an excerpt from _Scientific American_, January, 1985; In the section "Science and the Citizen" under the title "Simplified Simplex" pp. 54-55: ...Now Narendra Karmarkar of AT&T Bell Laboratories has invented a new algorithm that appears to solve such [linear programming] problems much faster than the simplex does.... ...Five years ago four mathematicians in the U.S.S.R. devised an algorithm called the ellipsoid method that is faster than the simplex method for certain rather artificial problems. In practice, however, such problems almost never arise, and almost all practical problems are solved many times faster by the simplex method than they are by the ellipsoid. Karmarkar's algorithm seems to win on both counts. It appears to improve on the practical performance of the simplex algorithm, and its theoretical, "worst case" performance is better than that of the ellipsoid method. ...It picks a starting point on the polygon and then attempts to improve the profit by taking a short cut through the polygon rather than merely moving along some edge....The Karmarkar algorithm is now being translated into high-speed machine language so that its full capabilities can be more fairly compared with those of the simplex. Apparently it is the ellipsoid method that was so heralded but bombed. The Karmarkar method seems to be catching on. Anyone have the method? Bell Labs must have published one of their little booklets on it. --------------------------------------------------------------------- USENET: ..!decvax!ittvax!sii!dmcnh!gts USMail: Guy T. Schafer, 14F Hampshire Dr, Nashua, NH 03063 AT&T: (603) 880-2069 Disclaimer: The content of this message is the sole responsibility of dmcnh!gts and does not necessarily reflect the policies of Datamedia. ---------------------------------------------------------------------