David L. Applegate is an American computer scientist known for his research on the
traveling salesperson problem
The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each cit ...
.
Education
Applegate graduated from the
University of Dayton in 1984, and completed his doctorate in 1991 from
Carnegie Mellon University
Carnegie Mellon University (CMU) is a private research university in Pittsburgh, Pennsylvania. One of its predecessors was established in 1900 by Andrew Carnegie as the Carnegie Technical Schools; it became the Carnegie Institute of Technology ...
, with a dissertation on
convex volume approximation In the analysis of algorithms, several authors have studied the computation of the volume of high-dimensional convex bodies, a problem that can also be used to model many other problems in combinatorial enumeration.
Often these works use a black bo ...
supervised by
Ravindran Kannan.
Career
Applegate worked on the faculty at
Rice University and at
AT&T Labs before joining
Google in New York City in 2016. His work on the
Concorde TSP Solver, described in a 1998 paper, won the Beale–Orchard-Hays Prize of the
Mathematical Optimization Society,
and his book ''The traveling salesman problem'' with the same authors won the
Frederick W. Lanchester Prize
The Frederick W. Lanchester Prize is an Institute for Operations Research and the Management Sciences prize (U.S. $5,000 cash prize and medallion) given for the best contribution to operations research and the management sciences published in Engli ...
in 2007.
He and
Edith Cohen won the
IEEE Communications Society's William R. Bennett Prize
for a 2006 research paper on robust network routing.
Another of his papers, on arithmetic without
carrying, won the 2013
George Pólya Award.
In 2013, he was named an AT&T Fellow.
With Guy Jacobsen and
Daniel Sleator, Applegate was the first to computerize the analysis of the pencil-and-paper game,
Sprouts.
Selected publications
References
External links
*
{{DEFAULTSORT:Applegate, David
Year of birth missing (living people)
Living people
American computer scientists
University of Dayton alumni
Carnegie Mellon University alumni
Rice University faculty