David Applegate
Topic: Biography
From HandWiki - Reading time: 3 min
David Applegate | |
|---|---|
| Academic background | |
| Education | University of Dayton (BS) Carnegie Mellon University (PhD) |
| Doctoral advisor | Ravindran Kannan |
| Academic work | |
| Discipline | Computer science |
| Sub-discipline | Convex volume approximation |
| Institutions | Rice University AT&T Labs |
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,[1] and completed his doctorate in 1991 from Carnegie Mellon University, with a dissertation on convex volume approximation supervised by Ravindran Kannan.[2]
Career
Applegate worked on the faculty at Rice University and at AT&T Labs before joining Google in New York City in 2016.[1] His work on the Concorde TSP Solver, described in a 1998 paper, won the Beale–Orchard-Hays Prize of the Mathematical Optimization Society,[3][1][ICM] and his book The traveling salesman problem with the same authors won the Frederick W. Lanchester Prize in 2007.[4][TSP] He and Edith Cohen won the IEEE Communications Society's William R. Bennett Prize for a 2006 research paper on robust network routing.[5][ToN] Another of his papers, on arithmetic without carrying, won the 2013 George Pólya Award.[6][CMJ] In 2013, he was named an AT&T Fellow.[1]
With Guy Jacobsen and Daniel Sleator, Applegate was the first to computerize the analysis of the pencil-and-paper game, Sprouts.[7][8]
Selected publications
| CMU. | Applegate, David; Jacobson, Guy; Sleator, Daniel (1991), Computer analysis of Sprouts, Computer Science Tech. Report CMU-CS-91-144, Carnegie Mellon University[6][CMJ] |
| OJC. | Applegate, David (May 1991), "A computational study of the job-shop scheduling problem", ORSA Journal on Computing 3 (2): 149–156, doi:10.1287/ijoc.3.2.149, http://www.math.uwaterloo.ca/~bico/papers/jobshop.pdf |
| ICM. | Applegate, David (1998), "On the solution of traveling salesman problems", Proceedings of the International Congress of Mathematicians, Vol. III (Berlin, 1998), Documenta Mathematica, pp. 645–656, http://www.mathunion.org/ICM/ICM1998.3/Main/17/Cook.MAN.ocr.pdf |
| TSP. | Applegate, David L. (2006), The traveling salesman problem: A computational study, Princeton Series in Applied Mathematics, Princeton, NJ: Princeton University Press, ISBN 978-0-691-12993-8[4][9] |
| ToN. | Applegate, David (December 2006), "Making routing robust to changing traffic demands: Algorithms and evaluation", IEEE/ACM Transactions on Networking 14 (6): 1193–1206, doi:10.1109/TNET.2006.886296[5] |
| CMJ. | Applegate, David; LeBrun, Marc (2012), "Carryless arithmetic mod 10", The College Mathematics Journal 43 (1): 43–50, doi:10.4169/college.math.j.43.1.043[6] |
References
- ↑ 1.0 1.1 1.2 1.3 "David Applegate", Research at Google, https://research.google.com/pubs/DavidApplegate.html, retrieved 2017-08-03
- ↑ David Applegate at the Mathematics Genealogy Project
- ↑ Past Winners of the Beale — Orchard-Hays Prize, Mathematical Optimization Society, http://www.mathopt.org/?nav=boh#winners, retrieved 2017-08-03.
- ↑ 4.0 4.1 "David L. Applegate", Recognizing Excellence: Award Recipients (Institute for Operations Research and the Management Sciences), https://www.informs.org/Recognizing-Excellence/Award-Recipients/David-L.-Applegate, retrieved 2017-08-03
- ↑ 5.0 5.1 The IEEE Communications Society William R. Bennett Prize, retrieved 2017-08-03
- ↑ 6.0 6.1 6.2 Applegate, David; Lebrun, Marc; Sloane, N. J. A. (2010), "Carryless Arithmetic Mod 10", George Pólya Awards (Mathematical Association of America), https://www.maa.org/programs/maa-awards/writing-awards/george-polya-awards/carryless-arithmetic-mod-10, retrieved 2017-08-03
- ↑ Gardner, Martin (2001), The Colossal Book of Mathematics: Classic Puzzles, Paradoxes, and Problems : Number Theory, Algebra, Geometry, Probability, Topology, Game Theory, Infinity, and Other Topics of Recreational Mathematics, W. W. Norton & Company, p. 491, ISBN 9780393020236, https://books.google.com/books?id=orz0SDEakpYC&pg=PA491
- ↑ Peterson, Ivars (2002), Mathematical Treks: From Surreal Numbers to Magic Circles, MAA Spectrum, Mathematical Association of America, p. 71, ISBN 9780883855379, https://books.google.com/books?id=4gWSAraVhtAC&pg=PA71
- ↑ Lenstra, Jan Karel; Shmoys, David (2009), "The traveling salesman problem: a computational study", SIAM Review 51 (4): 799–801
External links
- David Applegate publications indexed by Google Scholar
 |  |
EncycloReader
is supported by the 
KSF