ACM Press Release
The winner of the 10th Knuth Prize is David S. Johnson for seminal contributions to the theoretical and experimental analysis of combinatorial algorithms. David Johnson will receive the award and present the Knuth Prize Lecture at the 42th ACM Symposium on Theory of Computing held in Cambridge, Massachusetts, June 6-8, 2010.
David Johnson has made lasting contributions in the design of algorithms for hard combinatorial problems and in their analysis, both by theoretical and experimental methods, thereby laying out rigorous foundations for two important areas: approximation algorithms and experimental algorithms. His 1973 paper on the Approximation of combinatorial optimization problems set up the basic theoretical framework and approach for this area, and studied the approximation of some of the central optimization problems (clique, graph coloring, set cover, maximum satisfiability) that occupied the community for a long time subsequently, until their status was resolved almost 20 years later by the PCP theory, showing that Johnson's results were essentially optimal.
Johnson's work over the years has addressed the approximation of many other problems (scheduling, bin packing, TSP and many others). The area of approximation algorithms has grown and thrived over the years, and it has become one of the central areas of theoretical computer science. Besides the theoretical analysis, Johnson has written a set of highly influential papers on the experimental analysis of approximation algorithms that established equally rigorous and thorough standards for experimental work. His experimental papers on algorithms for the Traveling Salesman problem and on Simulated Annealing are paradigmatic and set an example for this kind of work.
David Johnson is well-known also for his many contributions to the early development of NP-completeness theory, including the concepts of strong NP-completeness and pseudopolynomial algorithms, for his book with Michael Garey that is the standard reference on NP-completeness, and for his ongoing columns that survey a variety of topics in theoretical computer science.
In addition to the great impact of his research, David Johnson has played an active leadership role in the theoretical computer science community, founding the annual ACM-SIAM Symposium on Discrete Algorithms (SODA) and the DIMACS Implementation Challenges, organizing and chairing many conferences, and by serving in multiple capacities in SIGACT and ACM.
The Knuth Prize for outstanding contributions to the foundations of computer science is awarded every 1½ years by the ACM Special Interest Group on Algorithms and Computation Theory (ACM-SIGACT) and the IEEE Technical Committee on the Mathematical Foundations of Computing. The Prize includes a $5000 award and a $1000 travel stipend (for travel to the award ceremony) paid by ACM SIGACT and IEEE TCMFC.
The Prize is awarded for major research accomplishments and contributions to the foundations of computer science over an extended period of time. The first Knuth Prize was presented at the 1996 ACM Symposium on Theory of Computing (STOC). Prizes are now awarded alternately at the ACM STOC and the IEEE Conference on Foundations of Computer Science (FOCS).
The Prize is named in honor and recognition of the extraordinary accomplishments of Prof. Donald Knuth, Emeritus at Stanford University. Prof. Knuth is best known for his ongoing multivolume series, The Art of Computer Programming, which played a critical role in establishing and defining Computer Science as a rigorous, intellectual discipline. Prof. Knuth has also made fundamental contributions to the subfields of analysis of algorithms, compilers, string matching, term rewriting systems, literate programming, and typography. His TeX and MF systems are widely accepted as standards for electronic typesetting. Prof. Knuth's work is distinguished by its integration of theoretical analyses and practical real-world concerns. In his work, theory and practice are not separate components of Computer Science, but rather he shows them to be inexorably linked branches of the same whole.
Past Winners
- 2008: Volker Strassen
- 2007: Nancy Lynch
- 2005: Mihalis Yannakakis
- 2003: Miklos Ajtai
- 2002: Christos Papadimitriou
- 2000: Jeffrey D. Ullman
- 1999: László Lovász
- 1997: Leslie G. Valiant
- 1996: Andrew C.-C. Yao
Posts
