This work is licensed under a
Creative Commons License.
|
Monday, May 02, 2005
Leonid Khachiyan (1952-2005)
Posted by Lance
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.9:10 AM #
-
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.
I tend to disagree. In the hindsight, the article is rather true. SDP relaxations turned out to be pretty powerful approximation heuristics for NP-complete problems and in fact work well on average for some important ones (for example, optimal multiuser detection in CDMA channels). Since the ellipsoid method can be used to solve convex optimization problems like SDP, what's wrong with the assertion that "Mr. Khachiyan's method is believed to offer an approach for the linear programming of computers to solve so-called "traveling salesman" problems"? Only that they used the word "linear"? This is not a big deal, since SDP is in fact a generalization of LP.
Peter
-
Or perhaps the words "is believed" are at issue. As I understand it, the article was written with little regard for the opinions of the actual scientists consulted...
-
A mathematician who proved a beautiful and highly influential result has passed away. I find it disappointing that Lance uses this news to not reflect on the contributions of Khachiyan and the result but to
make some point about New York Times coverage.
-
He was incredibly humble. A great loss to the community.
-
This is not a newspaper but a blog; so by definition it is about whatever Lance feels like talking about. If you want to find out more about Khachiyan, read an obituary instead. Personally I think the quote from the NYT is very interesting. Lance, please ignore that mean comment!!!!!!
Links to this post:
Weblog Home
Archives
