. We're a bit spoiled these days, what with Wikipedia pages with lists of NP-complete problems and online compendiums with references. But in ye olden days, when I was a grad student, if you had a reduction you needed to ponder, you went to Garey and Johnson. The book was an inspiration, and an invaluable research resource, to many. It's one of the most cited (the most cited?) references in computer science, and the book will rightly hold a special place in the history of computer science.
Wednesday, March 03, 2010
Congratulations to David Johnson, Knuth Prize Winner
I'm pleased to hear that David Johnson has won the Knuth Prize for "his contributions to theoretical and experimental analysis of algorithms." David has done a great many wonderful things, but I thought I'd highlight something that I imagine is underappreciated today, his book Computers and Intractability: A Guide to the Theory of NP-Completeness. We're a bit spoiled these days, what with Wikipedia pages with lists of NP-complete problems and online compendiums with references. But in ye olden days, when I was a grad student, if you had a reduction you needed to ponder, you went to Garey and Johnson. The book was an inspiration, and an invaluable research resource, to many. It's one of the most cited (the most cited?) references in computer science, and the book will rightly hold a special place in the history of computer science.
. We're a bit spoiled these days, what with Wikipedia pages with lists of NP-complete problems and online compendiums with references. But in ye olden days, when I was a grad student, if you had a reduction you needed to ponder, you went to Garey and Johnson. The book was an inspiration, and an invaluable research resource, to many. It's one of the most cited (the most cited?) references in computer science, and the book will rightly hold a special place in the history of computer science.
Subscribe to:
Post Comments (Atom)
3 comments:
Did he get the award because of the book? Excuse my ignorance, but I don't seem to be familiar with any of his work, except for the book...
I don't seem to be familiar with any of his work
David was a pioneer in the study of approximation algorithms for NP-hard optimization problems and the hardness of approximation. His 1973 STOC paper on approximation algorithms for combinatorial problems and his 1973 dissertation work on near-optimal approximation algorithms for bin-packing (FOCS 1972) has been hugely influential. He set the standard for the field as finding polynomial-time algorithms for which one can prove explicit approximation factors for NP-hard optimization problems. He developed a number of the best results known prior to the proof of the PCP theorem.
With Garey he developed the notion of "strongly" NP-complete numerical problems versus those NP-complete problems such as SubsetSum that are polynomial-time if the numbers are represented in unary.
The book was not just a summary of the state of the art that everyone knew. It also set the standard for how people thought about the problems. For example, it developed the notion of a PTAS. (Though the first PTAS was developed earlier.)
Funnily, I think the most cited book in our field is "The Art of Computer Programming" by Knuth himself...
Post a Comment