[Computational Complexity] Leonid Khachiyan (1952-2005)
Leonid Khachiyan passed away Friday at the age of 52. Khachiyan was best known for his 1979 ellipsoid algorithm giving the first polynomial-time algorithm to solve linear programming. While the simplex algorithm solved LP well in practice, Khachiyan gave the first formal proof of an efficient algorithm in the worst case. The ellipsoid algorithm also has applications for more general convex programming questions and can be used for approximating semidefinite programming used for example in the Goemans-Williamson algorithm approximating max-cut.
One of my first exposures to theoretical computer science came in high school when I read a New York Times article describing the algorithm. I later learned that article has become our standard example of bad science writing, focusing more on an unlikely link to NP-complete problems instead of just describing the important theoretical problem Khachiyan's algorithm does solve.
Mr. Khachiyan's method is believed to offer an approach for the linear programming of computers to solve so-called "traveling salesman" problems. Such problems are among the most intractable in all of mathematics…In the past, "traveling salesman" problems, including the efficient scheduling of airline crews or hospital nursing staffs, have been solved on computes using the "simplex method".New York Times science writing (and science writing in general) has vastly improved since those days.
Posted by Lance to Computational Complexity at 5/2/2005 09:10:00 AM