[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.)
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.
DIMACS Homepage