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.
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.
ReplyDeleteI 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...
ReplyDeleteA 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
ReplyDeletemake some point about New York Times coverage.
He was incredibly humble. A great loss to the community.
ReplyDeleteThis 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!!!!!!
ReplyDelete