David S. Johnson

David S. Johnson (1945-2016) was a prominent American computer scientist known for his work in algorithms, computational complexity theory, and optimization. His research and publications significantly influenced the field of computer science, particularly in approximation algorithms and NP-completeness theory. Johnson served as head of the Algorithms and Optimization Department at AT&T Bell Labs and later AT&T Labs Research. He co-authored the seminal book "Computers and Intractability: A Guide to the Theory of NP-Completeness" with Michael Garey, which became a foundational text in computational complexity theory. His contributions to the field include the development and analysis of approximation algorithms for various optimization problems, including bin packing, scheduling, and the traveling salesman problem. Johnson was also known for his work on experimental analysis of algorithms and his efforts to bridge the gap between theoretical computer science and practical applications. Throughout his career, Johnson served as editor-in-chief of the Journal of the ACM and was a fellow of the Association for Computing Machinery (ACM). His influence continues through the David S. Johnson Award for Best Student Paper, established by ACM SIGACT to recognize excellence in theoretical computer science research.

Readers consistently mention Johnson's "Computers and Intractability" as a reference text in computer science programs. Students highlight the clear explanations of complex NP-completeness concepts and the comprehensive catalog of NP-complete problems. Liked: - Clear writing style for technical concepts - Organized problem classification system - Practical examples that connect theory to applications - In-depth coverage of reductions between problems Disliked: - Dense mathematical notation requires strong background - Some readers found proofs too concise - Limited coverage of newer developments (post-1979) - High price point for current editions On Goodreads, "Computers and Intractability" maintains a 4.26/5 rating from 648 readers. Amazon reviews average 4.5/5 from 112 reviewers. Multiple readers note using it as both a textbook and ongoing reference throughout their careers. One researcher wrote: "The reduction techniques outlined by Johnson remain the clearest presentation of this material I've encountered in 20 years of computer science."

Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) A comprehensive textbook that explains computational complexity theory and NP-completeness, including detailed proofs and a catalog of NP-complete problems.

Near-Optimal Bin Packing Algorithms (1974) A doctoral dissertation examining algorithmic approaches to the bin packing problem and establishing performance bounds for various heuristic methods.

The NP-Completeness Column: An Ongoing Guide (1981-1992) A series of articles published in the Journal of Algorithms providing updates and new developments in complexity theory and NP-completeness research.

Local Optimization and the Traveling Salesman Problem (1988) A research paper analyzing local search techniques for solving the traveling salesman problem and introducing the Lin-Kernighan heuristic improvements.

Experimental Analysis of Algorithms (1996) A methodological paper detailing approaches for conducting rigorous experimental evaluations of algorithmic performance and efficiency.

Stephen Cook writes about computational complexity and algorithmic theory, sharing many research interests with Johnson. His work on the P versus NP problem and NP-completeness theory builds directly on concepts Johnson explored.

Richard Karp focuses on combinatorial algorithms and computational complexity, following similar paths to Johnson's research. He has made contributions to network flow problems and algorithmic efficiency that complement Johnson's work on approximation algorithms.

Michael Garey coauthored seminal works on computational intractability with Johnson. His research on NP-completeness and optimization problems aligns with Johnson's theoretical computer science focus.

Christos Papadimitriou writes about algorithms, complexity theory, and optimization, covering terrain parallel to Johnson's areas of study. His work on computational aspects of game theory and economics extends some of the theoretical foundations Johnson established.

Jon Kleinberg researches algorithms, particularly in the context of networks and information systems. His publications on approximation algorithms and computational social science build upon Johnson's foundational contributions to these fields.