David S. Johnson: In Memoriam

David S. Johnson, a leading expert in the area of computational complexity and the design and analysis of algorithms, died Tuesday. Since 2014, Johnson was a visiting professor at Columbia University.

The winner of the 2010 Knuth Prize ^[1] for his contributions to theoretical and experimental analysis of algorithms, Johnson helped lay the foundation for algorithms used to address optimization problems, in which a best solution is sought among a large set of possible solutions to a problem. His papers on the experimental analysis of approximation algorithms were influential in establishing rigorous standards for algorithms that find an approximately optimal rather than exactly optimal solution. Such approximation algorithms play an important role within computer science both in theory and in practice.

Johnson researched and contributed to a range of foundational topics in both mathematics and computer science, including combinatorial optimization, network design, routing and scheduling, facility location, bin packing, graph coloring, and the Traveling Salesman Problem.

It is however his pioneering work on NP-completeness for which he is best known. He was one of the first to investigate NP-completeness, which deals with problems that are believed to be unsolvable within a reasonable amount of time in the worst case. His book, Computers and Intractability: A Guide to the Theory of NP-Completeness, coauthored with Michael Garey and written in 1979, has been called a classic for its rigorous treatment of NP completeness and for its clear, concise exposition. The book is one of the most cited references in all of computer science, with over 55,000 citations. Johnson continued to write on NP-completeness throughout his career, maintaining a column on the subject from 1982 until 1992 in the Journal of Algorithms.

Born December 9, 1945, Johnson attended Amherst as an undergraduate studying mathematics and went on to MIT where he earned a PhD in mathematics in 1973 for his thesis Near-Optimal Bin Packing Algorithms. The same year, he started his long and productive career at Bell Labs (and later AT&T Research) that would last until 2014. During this time, he published continuously, including several books and well over 100 papers and articles, many of which concern the best ways to cope with computational intractability and his developing interest in the interplay between theoretical and experimental analysis in computer science.

Johnson was an active member and leader in the theoretical computer science community, founding the Symposium on Discrete Algorithms (SODA), a conference that has become a top theory venue; for 25 years he served as SODA’s committee chair. He created also the DIMACS (Center for Discrete Mathematics and Theoretical Computer Science) Implementation Challenges. His work within the community was unflagging. He served on the ACM Council as Member-at-Large (1996-2004), chaired ACM SIGACT (1987-1991), edited the Journal of the Association for Computing Machinery (1983-1987), and he served as associate editor of ACM Transactions on Algorithms (TALG) since its founding in 2004.

In 2014, Johnson joined Columbia’s computer science faculty as a visiting professor, teaching CS students and interacting with faculty.

“We will miss David very much. He was a wonderful colleague and mentor for students,” said Julia Hirschberg, chair of Columbia’s Computer Science department.

In addition to the Knuth Prize awarded to him in 2010, Johnson is a 1995 Fellow of the Association for Computing Machinery and was just this year was elected to the National Academy of Engineering. Johnson has an Erdős number of 2.

These awards do not do justice to his many contributions to the field of computer science, both written and in private consultation with colleagues and students. David Johnson will be missed for his expertise and for the modest and unassuming way in which he set about to better understand and communicate to others the foundational topics in computer science.

– Linda Crane