colonel@gloria.UUCP (George Sicherman) (12/26/84)
> > There has been a great deal of media "hype" on this algorithm, somewhat > > similar to the hype which followed the Khatchian algorithm 4 years > > ago, and which turned out to be highly exaggerated. The value of the > > Karmaker algorithm remains to be seen. > > What was the Khatchian algorithm? How was it hyped and what were its > limitations? Khatchian's algorithm solved the linear programming problem in polynomial time (third or fourth power, I think). This is better than the worst case for the Simplex Method, which uses exponential time. It's an important theoretical result. It's unimportant in practice, since the Simplex Method usually runs in linear time. The mass media cannot distinguish between theoretical results and practical results. -- Col. G. L. Sicherman ...seismo!rochester!rocksanne!rocksvax!sunybcs!gloria!colonel