David L. Applegate is an American computer scientist known for his research on the traveling salesperson problem.
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 |
Education edit
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 edit
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 edit
| 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; Cook, William (May 1991), "A computational study of the job-shop scheduling problem" (PDF), ORSA Journal on Computing, 3 (2): 149–156, doi:10.1287/ijoc.3.2.149
|
| ICM. | Applegate, David; Bixby, Robert E.; Chvátal, Vašek; Cook, William J. (1998), "On the solution of traveling salesman problems", Proceedings of the International Congress of Mathematicians, Vol. III (Berlin, 1998) (PDF), Documenta Mathematica, pp. 645–656, MR 1648194
|
| 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 2286675[4][9]
|
| 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, doi:10.1109/TNET.2006.886296, S2CID 27498169[5]
|
| CMJ. | Applegate, David; LeBrun, Marc; Sloane, N. J. A. (2012), "Carryless arithmetic mod 10", The College Mathematics Journal, 43 (1): 43–50, arXiv:1008.4633, doi:10.4169/college.math.j.43.1.043, MR 2875555, S2CID 10952221[6]
|
References edit
- ^ a b c d "David Applegate", Research at Google, retrieved 2017-08-03
- ^ David Applegate at the Mathematics Genealogy Project
- ^ Past Winners of the Beale — Orchard-Hays Prize, Mathematical Optimization Society, retrieved 2017-08-03.
- ^ a b "David L. Applegate", Recognizing Excellence: Award Recipients, Institute for Operations Research and the Management Sciences, retrieved 2017-08-03
- ^ a b The IEEE Communications Society William R. Bennett Prize, retrieved 2017-08-03
- ^ a b c Applegate, David; Lebrun, Marc; Sloane, N. J. A. (2010), "Carryless Arithmetic Mod 10", George Pólya Awards, Mathematical Association of America, arXiv:1008.4633, 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
- ^ Peterson, Ivars (2002), Mathematical Treks: From Surreal Numbers to Magic Circles, MAA Spectrum, Mathematical Association of America, p. 71, ISBN 9780883855379
- ^ Lenstra, Jan Karel; Shmoys, David (2009), "The traveling salesman problem: a computational study", SIAM Review, 51 (4): 799–801, MR 2573947
External links edit
- David Applegate publications indexed by Google Scholar