David Johnson to Receive Knuth Prize

AT&T Labs researcher David Johnson will receive this year’s Knuth Prize from the ACM “for his contributions to theoretical and experimental analysis of algorithms”.  While Johnson is best known for his NP-Completeness book with Michael Garey, he has had an extraordinarily influential career in both the theory of approximation algorithms and in research on experimental evaluation of algorithms.  From the announcement:

The ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) will present its 2009 Knuth Prize to David S. Johnson of AT&T Labs for his contributions to theoretical and experimental analysis of algorithms.  Johnson’s innovations helped lay the foundation for algorithms used to address optimization problems, which involve the process of finding the best solution from all feasible solutions.  In addition, Johnson made many contributions to the early development of NP-completeness theory, which helps identify those problems that are hard to solve efficiently. The Knuth Prize, named in honor of Donald Knuth of Stanford University who has been called the “father” of the analysis of algorithms, will be presented at the ACM Symposium on Theory of Computing (STOC) June 6-8, 2010, in Cambridge, MA, where Johnson will present the Knuth Prize Lecture.

I got to know David almost 20 years ago when I agreed to coordinate one of his DIMACS Implementation Challenges.  This cooperation resulted in a book and, a decade later, a special issue of Discrete Applied Mathematics (with Anuj Mehortra). These Challenges are one of the ways David has explored issues in the evaluation of algorithms.  I had the chance recently to give a presentation on the effect of those Challenges.  David has had an enormous influence on me as I think about how to provide a firmer underpinning to the experimental analysis of algorithms and the way individuals and a field report on results.  This Prize makes me wish I had more time to spend on completing a planned system for reporting and confirming computational results.

I guess I am only surprised that David hadn’t already won this prize!  Very well deserved.