David Applegate
{{short description|American computer scientist}}
{{For|the geologist|David Applegate (geologist)}}
{{Infobox academic|name=David Applegate|education=University of Dayton (BS)
Carnegie Mellon University (PhD)|discipline=Computer science|doctoral_advisor=Ravindran Kannan|workplaces=Rice University
AT&T Labs
Google|sub_discipline=Convex volume approximation}}
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,{{r|g}} and completed his doctorate in 1991 from Carnegie Mellon University, with a dissertation on convex volume approximation supervised by Ravindran Kannan.{{r|mgp}}
Career
Applegate worked on the faculty at Rice University and at AT&T Labs before joining Google in New York City in 2016.{{r|g}} His work on the Concorde TSP Solver, described in a 1998 paper, won the Beale–Orchard-Hays Prize of the Mathematical Optimization Society,{{r|boh|g}}{{ran|ICM}}
and his book The traveling salesman problem with the same authors won the Frederick W. Lanchester Prize in 2007.{{r|lanchester}}{{ran|TSP}}
He and Edith Cohen won the IEEE Communications Society's William R. Bennett Prize for a 2006 research paper on robust network routing.{{r|bennett}}{{ran|ToN}} Another of his papers, on arithmetic without carrying, won the 2013 George Pólya Award.{{r|polya}}{{ran|CMJ}} In 2013, he was named an AT&T Fellow.{{r|g}}
With Guy Jacobsen and Daniel Sleator, Applegate was the first to computerize the analysis of the pencil-and-paper game, Sprouts.{{r|colossal|treks}}
Selected publications
{{rma|CMU|{{citation|first1=David|last1=Applegate|first2=Guy|last2=Jacobson|first3=Daniel|last3=Sleator|author3-link=Daniel Sleator|title=Computer analysis of Sprouts|series=Computer Science Tech. Report CMU-CS-91-144|publisher=Carnegie Mellon University|year=1991}}{{r|polya}}{{ran|CMJ}}|tw=2.5em}}
{{rma|OJC|{{citation
| last1 = Applegate | first1 = David
| last2 = Cook | first2 = William | author2-link = William J. Cook
| date = May 1991
| doi = 10.1287/ijoc.3.2.149
| issue = 2
| journal = ORSA Journal on Computing
| pages = 149–156
| title = A computational study of the job-shop scheduling problem
| url = http://www.math.uwaterloo.ca/~bico/papers/jobshop.pdf
| volume = 3}}|tw=2.5em}}
{{rma|ICM|{{citation
| last1 = Applegate
| first1 = David
| last2 = Bixby
| first2 = Robert E.
| author2-link = Robert E. Bixby
| last3 = Chvátal
| first3 = Vašek
| author3-link = Václav Chvátal
| last4 = Cook
| first4 = William J.
| author4-link = William J. Cook
| title = Proceedings of the International Congress of Mathematicians, Vol. III (Berlin, 1998)
| series = Documenta Mathematica
| mr = 1648194
| pages = 645–656
| contribution = On the solution of traveling salesman problems
| url = http://www.mathunion.org/ICM/ICM1998.3/Main/17/Cook.MAN.ocr.pdf
| year = 1998
| access-date = 2017-08-04
| archive-date = 2017-07-13
| archive-url = https://web.archive.org/web/20170713121043/http://www.mathunion.org/ICM/ICM1998.3/Main/17/Cook.MAN.ocr.pdf
| url-status = dead
}}|tw=2.5em}}
{{rma|TSP|{{citation
| last1 = Applegate | first1 = David L.
| last2 = Bixby | first2 = Robert E. | author2-link = Robert E. Bixby
| last3 = Chvátal | first3 = Vašek | author3-link = Václav Chvátal
| last4 = Cook | first4 = William J. | author4-link = William J. Cook
| isbn = 978-0-691-12993-8
| location = Princeton, NJ
| mr = 2286675
| publisher = Princeton University Press
| series = Princeton Series in Applied Mathematics
| title = The traveling salesman problem: A computational study
| year = 2006}}{{r|lanchester|sirev}}|tw=2.5em}}
{{rma|ToN|{{citation
| last1 = Applegate | first1 = David
| last2 = Cohen | first2 = Edith | author2-link = Edith Cohen
| date = December 2006
| doi = 10.1109/TNET.2006.886296
| issue = 6
| journal = IEEE/ACM Transactions on Networking
| pages = 1193–1206
| title = Making routing robust to changing traffic demands: Algorithms and evaluation
| volume = 14| s2cid = 27498169
}}{{r|bennett}}|tw=2.5em}}
{{rma|CMJ|{{citation
| last1 = Applegate | first1 = David
| last2 = LeBrun | first2 = Marc
| last3 = Sloane | first3 = N. J. A. | author3-link = Neil Sloane
| doi = 10.4169/college.math.j.43.1.043
| issue = 1
| journal = The College Mathematics Journal
| mr = 2875555
| pages = 43–50
| title = Carryless arithmetic mod 10
| volume = 43
| year = 2012| arxiv = 1008.4633| s2cid = 10952221
}}{{r|polya}}|tw=2.5em}}
References
{{reflist|30em|refs=
{{citation|url=http://www.mathopt.org/?nav=boh#winners|title=Past Winners of the Beale — Orchard-Hays Prize|publisher=Mathematical Optimization Society|accessdate=2017-08-03}}.
{{citation|url=https://www.informs.org/Recognizing-Excellence/Award-Recipients/David-L.-Applegate|title=David L. Applegate|work=Recognizing Excellence: Award Recipients|publisher=Institute for Operations Research and the Management Sciences|accessdate=2017-08-03}}
{{citation|url=https://www.maa.org/programs/maa-awards/writing-awards/george-polya-awards/carryless-arithmetic-mod-10|archive-url=https://web.archive.org/web/20131220033742/http://www.maa.org/programs/maa-awards/writing-awards/george-polya-awards/carryless-arithmetic-mod-10|url-status=dead|archive-date=December 20, 2013|title=Carryless Arithmetic Mod 10|work=George Pólya Awards|publisher=Mathematical Association of America|accessdate=2017-08-03|last1=Applegate|first1=David|last2=Lebrun|first2=Marc|last3=Sloane|first3=N. J. A.|year=2010|arxiv=1008.4633}}
| last1 = Lenstra | first1 = Jan Karel
| last2 = Shmoys | first2 = David
| issue = 4
| journal = SIAM Review
| mr = 2573947
| pages = 799–801
| title = The traveling salesman problem: a computational study
| volume = 51
| year = 2009}}
}}
External links
- {{Google Scholar id|Zc0rg5EAAAAJ}}
{{Authority control}}
{{DEFAULTSORT:Applegate, David}}
Category:Year of birth missing (living people)
Category:American computer scientists
Category:University of Dayton alumni