David Applegate

David L. Applegate is an American computer scientist known for his research on the traveling salesperson problem.

Education

Applegate graduated from the University of Dayton in 1984, and completed his doctorate in 1991 from Carnegie Mellon University, with a dissertation on convex volume approximation supervised by Ravindran Kannan.

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,[ICM] and his book The traveling salesman problem with the same authors won the Frederick W. Lanchester Prize in 2007.[TSP] He and Edith Cohen won the IEEE Communications Society's William R. Bennett Prize for a 2006 research paper on robust network routing.[ToN] Another of his papers, on arithmetic without carrying, won the 2013 George Pólya Award.[CMJ] 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.

CMU.	Applegate, David; Jacobson, Guy; Sleator, Daniel (1991), Computer analysis of Sprouts, Computer Science Tech. Report CMU-CS-91-144, Carnegie Mellon University[CMJ]

OJC.	Applegate, David; Cook, William (May 1991), (PDF), ORSA Journal on Computing, 3 (2): 149–156, doi:

ICM.	Applegate, David; Bixby, Robert E.; Chvátal, Vašek; Cook, William J. (1998), "On the solution of traveling salesman problems", (PDF), Documenta Mathematica, pp. 645–656, MR , archived from (PDF) on 2017-07-13

TSP.	Applegate, David L.; Bixby, Robert E.; Chvátal, Vašek; Cook, William J. (2006), The traveling salesman problem: A computational study, Princeton Series in Applied Mathematics, Princeton, NJ: Princeton University Press, ISBN 978-0-691-12993-8, MR

ToN.	Applegate, David; Cohen, Edith (December 2006), "Making routing robust to changing traffic demands: Algorithms and evaluation", IEEE/ACM Transactions on Networking, 14 (6): 1193–1206, Bibcode:, doi:, S2CID

CMJ.	Applegate, David; LeBrun, Marc; Sloane, N. J. A. (2012), "Carryless arithmetic mod 10", The College Mathematics Journal, 43 (1): 43–50, arXiv:, doi:, MR , S2CID