Obituaries: David Stifler Johnson

By Mihalis Yannakakis, Cliff Stein

David Stifler Johnson, a leader in theoretical computer science, passed away on March 8, 2016, at the age of 70. David is well known for his fundamental contributions to NP-completeness theory, optimization and approximation algorithms, and the experimental analysis of algorithms.

Born December 9, 1945, David received a B.A. in mathematics from Amherst College in 1967 and an M.S. in mathematics from the Massachusetts Institute of Technology (MIT) in 1968. After serving in the U.S. Army for two years, he returned to MIT, where he obtained his Ph.D. in 1973. In his Ph.D. thesis, “Near-Optimal Bin Packing Algorithms,” David analyzed the performance of efficient bin packing algorithms, proving tight results on the proximity of the solutions they compute to the optimal solutions.

After his graduation, David joined AT&T Bell Laboratories, where he worked in the Mathematical Sciences Research Center from 1973 until 1996. He was head of the Mathematical Foundations of Computing Department from 1988 onwards. When AT&T split in 1996, David joined AT&T Labs Research, serving as head of the Algorithms and Optimization Research Department until 2013. He then joined the faculty of Columbia University as a visiting professor in the Department of Computer Science.

David was a major contributor to the early development of the theory and applications of NP-completeness. This theory established a close relationship between many seemingly-intractable problems that arise in a diverse range of fields and are believed to be unsolvable in polynomial time. David (and his collaborators) showed the NP-completeness of many basic problems from a variety of areas and introduced central concepts, e.g. the notions of strong NP-completeness and pseudopolynomial algorithms, that identify more specifically the source of intractability. However, David’s greatest impact in this field is through his book, Computers and Intractability: A Guide to the Theory of NP-Completeness, coauthored by Michael R. Garey and published in 1979. In addition to presenting the fundamentals of NP-completeness theory, the book contains an extensive, systematic compendium of NP-complete problems known at the time, making it an invaluable reference. It has served generations of computer scientists and engineers as a handbook for differentiating computational problems that are solvable by practical, efficient methods from those that are not, and is one of the most cited references in all of computer science. A year after its publication, David and Garey received the Operations Research Society of America’s Lanchester Prize. 

Beginning in 1982, David wrote “The NP-completeness Column: an Ongoing Guide,” a regular series of articles in the Journal of Algorithms and later The ACM Transactions on Algorithms, which covered new developments in the theory of NP-completeness and in related areas of algorithms and complexity theory.

David’s early work was also instrumental in laying the foundation for the theory of approximation algorithms, efficient algorithms that compute nearly optimal solutions to hard optimization problems. Starting with his Ph.D. thesis, he designed and analyzed approximation algorithms for many important problems, including packing and scheduling. David’s 1973 paper, “Approximation Algorithms for Combinatorial Problems,” is especially significant. In this paper, he studied central combinatorial problems like clique, graph coloring, set cover, and maximum satisfiability. He noted that, although these problems are polynomially equivalent in terms of reaching an optimal solution, they are very different with respect to efficiently finding good approximate solutions; this raised the question of how to classify the approximability of these and other hard combinatorial optimization problems. The area of approximation algorithms has flourished since then, building on the work of David and others, and continues to be one of the most active fields in theoretical computer science. The questions raised in David’s 1973 paper eventually led to the development of the deep theory of probabilistically-checkable proofs some 20 years later, demonstrating that his algorithms were essentially optimal.

David also played a prominent role in laying out rigorous foundations for the experimental analysis of algorithms. In a series of highly influential papers in the late 80s and 90s, he performed a comprehensive experimental analysis of different algorithms for important, well-studied problems, most notably the famous travelling salesman problem, and of general methodologies like simulated annealing. His papers are emblematic of rigor and thoroughness, and set the standard for this kind of work. David also initiated and led a series of annual Implementation Challenges at the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) that fostered rigorous experimental research in the algorithms community.

Besides his personal research, David was heavily involved in the theoretical computer science community, and has greatly impacted the field’s growth. In 1990, he founded the ACM-SIAM Symposium on Discrete Algorithms (SODA), a top venue for research in the field, and served as steering committee chair for 25 years. David organized and chaired many other conferences, including the Federated Computing Research Conference and the ACM Symposium on Theory of Computing. He led the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) from 1987 to 1991, initiated several awards, chaired and served on many ACM and SIAM committees, and continued to impact the theoretical computer science community throughout his career. In recognition of his extraordinary contributions, David received the first SIGACT Distinguished Service Prize for his “selfless dedication and personal initiative in serving the Computer Science Theory community.”

Numerous honors and prizes commemorate David’s research. He was named a SIAM Fellow in 2009, and was also recognized as an ACM Fellow and an AT&T Fellow. David received the Donald E. Knuth Prize for his contributions to the theoretical and experimental analysis of algorithms, and was elected to the National Academy of Engineering for his “contributions to the theory and practice of optimization and approximation algorithms.”

David was a very generous, humble, and modest person. He cared deeply about people, including the members of his department, his colleagues, and researchers from all over the world who often contacted him with questions on NP-completeness, experimental analysis, purported proofs of \(\textrm{P=NP}\) or \(\textrm{P≠NP,}\) and other topics. David was a great mentor to young researchers, including the many students that interned in the Labs during his career. He advocated for and advanced the careers of countless members of the community, and kept a list of young researchers who should be chosen for conference program committees. He was an inspiration to all of his colleagues and will be greatly missed.

Mihalis Yannakakis is Hudson Professor of Computer Science at Columbia University. He was a friend and colleague of David at Bell Labs for many years. Cliff Stein is a professor of computer science and industrial engineering and operations research at Columbia University. He was David’s summer intern in 1991; David was a mentor, colleague, and friend ever since.