In Memoriam: David S. Johnson 1945–2016

David S. Johnson, an American computer scientist specializing in algorithms and optimization who received the 2010 Donald E. Knuth Prize for his contributions to theoretical and experimental analysis of algorithms, died March 8 at the age of 70.

Born Dec. 9, 1945, Johnson earned a B.A. in mathematics at Amherst College before going on to earn his master’s degree in that discipline from the Massachusetts Institute of Technology (MIT) with the thesis "Look-Ahead Strategies in One-Person Games with Randomly Generated Game Trees." For his doctorate in 1973, also in mathematics from MIT, Johnson submitted the thesis "Near-Optimal Bin Packing Algorithms," which suggested such algorithms would "run in low-order polynomial time."  

Also, in 1973, Johnson began working with AT&T Bell Laboratories as a member of the technical staff. In 1988, he was named head of the organization’s Mathematical Foundations of Computing Department, and in 1996, he became head of the Algorithms & Optimization Research Department of AT&T Labs–Research. During 2013, Johnson served as a Distinguished Member of the Technical Staff of AT&T Labs–Research.

On the academic side, Johnson spent part of 1978 as a visiting lecturer at the Rutgers University Computer Science Department. During the 1980–81 school term, he was a visiting lecturer at the University of Wisconsin’s Computer Science Department. Since 2014, he had been serving as a Visiting Professor to the Columbia University Computer Science Department.

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, he made many contributions to the early development of NP-completeness theory, which helps identify those problems that are hard to solve efficiently.

He also authored a set of highly influential papers on the experimental analysis of approximation algorithms.  This research established equally rigorous standards for experimental algorithms, which focus on implementations as the standard of value and provide the key to the transfer of research results from paper to production code. 

Johnson wrote, edited, or contributed to a number of books, including the 1979 "Computers and Intractability: A Guide to the Theory of NP-Completeness" (co-authored with Michael Garey), one of the most-cited references in computer science with more than 55,000 citations, according to Google Scholar.

He started writing a column (which he referred to as "An Ongoing Guide")on NP-completeness in 1982 in the Journal of Algorithms, and continued until the publication was halted in 1992; it was revived for the journal ACM Transactions on Algorithms, which launched in 2004.

Johnson founded the Symposium on Discrete Algorithms (SODA), and served as a committee chair for 25 years; today, the conference is known as the ACM-SIAM Symposium on Discrete Algorithms, and is jointly sponsored by the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) and the Society for Industrial and Applied Mathematics (SIAM) Activity Group on Discrete Algorithms. The event has been held annually since 1990.

He created also the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) Implementation Challenges, which "address questions of determining realistic algorithm performance where worst case analysis is overly pessimistic and probabilistic models are too unrealistic: experimentation can provide guides to realistic algorithm performance where analysis fails."

Johnson served on the ACM Council as Member-at-Large from 1996 to 2004, chaired SIGACT from 1987 to 1991, edited the Journal of the ACM from 1983 to 1987, and served as associate editor of ACM Transactions on Algorithms (TALG) from its founding in 2004.

In addition to the Knuth Award, Johnson was named an ACM Fellow in 1995 for "fundamental contributions to the theories of approximation algorithms and computational complexity, and for outstanding service to ACM." Johnson received the first SIGACT Distinguished Service Prize in 1997, for his "selfless dedication and personal initiative in serving the Computer Science Theory community." He was named an AT&T Fellow in 2005, a SIAM Fellow in 2009, and was elected to the National Academy of Engineering this year for his "contributions to the theory and practice of optimization and approximation algorithms.

Lance Fortnow, professor and chair of the School of Computer Science in the Georgia Institute of Technology College of Computing, recalled meeting Johnson as a doctoral student in the 1980s. "During one of his visits to MIT, David asked me my opinions on what should or should not be in the chapter. For someone as senior and important as David Johnson, getting my opinion as a student made a tremendous impression and we’ve been great colleagues from that time forward."

Years later, Fortnow said, he worked with Johnson "closely on various SIGACT activities. David never missed a STOC (the annual ACM Symposium on Theory of Computing) and we always invited him to the SIGACT Executive Committee dinners, not because he had an official role, but because he was David Johnson. I truly respected and admired David and am glad I could call him a friend. We’ll miss him deeply. STOC and SODA just won’t be the same without him."

Lawrence M. Fisher is Senior Editor/News for ACM magazines.