David L. Applegate is an American computer scientist known for his research on the
traveling salesperson problem
In the Computational complexity theory, theory of computational complexity, the travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible ...
.
Education
Applegate graduated from the
University of Dayton
The University of Dayton (UD) is a Private university, private, Catholic research university in Dayton, Ohio, United States. Founded in 1850 by the Society of Mary (Marianists), Society of Mary, it is one of three Marianist universities in the U ...
in 1984, and completed his doctorate in 1991 from
Carnegie Mellon University
Carnegie Mellon University (CMU) is a private research university in Pittsburgh, Pennsylvania, United States. The institution was established in 1900 by Andrew Carnegie as the Carnegie Technical Schools. In 1912, it became the Carnegie Institu ...
Rice University
William Marsh Rice University, commonly referred to as Rice University, is a Private university, private research university in Houston, Houston, Texas, United States. Established in 1912, the university spans 300 acres.
Rice University comp ...
and at
AT&T Labs
AT&T Labs, Inc. (formerly AT&T Laboratories, Inc.) is the research & development division of AT&T, the telecommunications company. It employs some 1,800 people in various locations, including: Bedminster, New Jersey; Middletown Township, New J ...
before joining
Google
Google LLC (, ) is an American multinational corporation and technology company focusing on online advertising, search engine technology, cloud computing, computer software, quantum computing, e-commerce, consumer electronics, and artificial ...
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
Edith Cohen
Edith Cohen (Hebrew: אדית כהן; born May 21, 1966) is an Israeli and American computer scientist specializing in data mining and algorithms for big data. She is also known for her research on peer-to-peer networks. She works for Google in M ...
won the
IEEE Communications Society
The Institute of Electrical and Electronics Engineers (IEEE) is an American 501(c)(3) public charity professional organization for electrical engineering, electronics engineering, and other related disciplines.
The IEEE has a corporate office i ...
'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
The George Pólya Award is presented annually by the Mathematical Association of America (MAA) for articles of expository excellence that have been published in The College Mathematics Journal. The award was established in 1976, and up to two aw ...
. In 2013, he was named an AT&T Fellow.
With Guy Jacobsen and
Daniel Sleator
Daniel Dominic Kaplan Sleator (born 10 December 1953) is a professor of computer science at Carnegie Mellon University, Pittsburgh, United States. In 1999, he won the ACM Paris Kanellakis Award (jointly with Robert Tarjan) for the splay tree d ...
, Applegate was the first to computerize the analysis of the pencil-and-paper game, Sprouts.