March 2016
By any estimation, David Johnson’s influence on the field of computer science was profound. Since his death on March 8, colleagues and friends have reflected on the role that David played in shaping the field, particularly related to theoretical and experimental analysis of algorithms.
David’s influence on DIMACS was no less profound. He was instrumental in the development and evolution of DIMACS as an NSF Science and Technology Center from its earliest days. Over the 27 years DIMACS has been in operation, David was a steadfast supporter and dedicated leader of many programs contributing to DIMACS and the community it serves. In early years, he was co-organizer of DIMACS special years on Graph Theory and Algorithms, Combinatorial Optimization, and Computational Intractability. He also helped guide many other special programs as a longstanding member of the DIMACS Executive Committee.
Most notable among his many contributions to DIMACS are the Implementation Challenges that David established to help understand and improve the practical performance of algorithms for important problems, particularly those that are hard in the theoretical sense. The Challenges aid in determining realistic algorithm performance where worst-case analysis is overly pessimistic and probabilistic models are too unrealistic. In such cases, experimentation can provide insight into realistic algorithm performance where analysis fails.
There have been eleven Implementation Challenges since they began in 1990, and David played an important role in each of them. Some were on problems that are theoretically hard such as the Traveling Salesman, Steiner Tree, and Graph Partitioning problems, while others were on important polynomially solvable problems like the Shortest Path and Network Flow problems. Running a successful challenge requires substantial lead time and behind-the-scenes planning to set up libraries of test problem instances and instance generators, interact with competing teams, and establish practices to meaningfully compare running times across platforms in order to establish a common vision of the “state of the art.” Equally important is ensuring a collaborative environment that encourages researchers to exchange ideas, learn from each other, combine methods, and focus on the most promising directions. Under David’s leadership and guidance, the Implementation Challenges have led to new breakthroughs, faster algorithms, better communication between users and designers of algorithmic methods, and a host of DIMACS book volumes detailing what was learned.
These activities are just a small part of what made David such an important member of our community and small examples of why he will be missed so much. Others have their own remembrances and expressions of gratitude. Among them are a memorial by Lawrence Fisher in Communications of the ACM, another from the computer science department at Columbia, and tributes by Lance Fortnow and by Dick Lipton and Ken Regan in their blogs. Adding to these is this personal expression from DIMACS Director Rebecca Wright, “In addition to his extensive research accomplishments, David was a major voice for theoretical computer science, particularly for experimental analysis of algorithms. He played a leading role at DIMACS from its inception, most notably through the creation and shepherding of the DIMACS Implementation Challenges. He was also one of the nicest people I know, which in his professional life translated to being generous with his time, focused on development of community, and supportive of colleagues both junior and senior. We will miss him greatly.”
Attendees of the 11th DIMACS Implementation Challenge in 2014. (David Johnson is sixth from left.)