David Applegate

Short description: American computer scientist

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
Google

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

## Contents

* 1 Education
* 2 Career
* 3 Selected publications
* 4 References
* 5 External links

## 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. ↑ 1.0 1.1 1.2 1.3 "David Applegate", Research at Google, https://research.google.com/pubs/DavidApplegate.html, retrieved 2017-08-03
2. ↑ David Applegate at the Mathematics Genealogy Project
3. ↑ Past Winners of the Beale — Orchard-Hays Prize, Mathematical Optimization Society, http://www.mathopt.org/?nav=boh#winners, retrieved 2017-08-03 .
4. ↑ 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. ↑ 5.0 5.1 The IEEE Communications Society William R. Bennett Prize, retrieved 2017-08-03
6. ↑ 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
7. ↑ 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
8. ↑ 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
9. ↑ 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

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/David Applegate. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Biography:David_Applegate&oldid=3399994"