David Applegate

For the geologist, see David Applegate (geologist).
David Applegate
Academic background
EducationUniversity of Dayton (BS)
Carnegie Mellon University (PhD)
Ravindran Kannan
Academic work
DisciplineComputer science
Sub-discipline
Convex volume approximation
InstitutionsRice University
AT&T Labs
Google

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; 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, archived from the original (PDF) on 2017-07-13, retrieved 2017-08-04
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, Bibcode:2006ITNet..14.1193A, 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

  1. ^ a b c d "David Applegate", Research at Google, retrieved 2017-08-03
  2. ^ David Applegate at the Mathematics Genealogy Project
  3. ^ Past Winners of the Beale — Orchard-Hays Prize, Mathematical Optimization Society, retrieved 2017-08-03.
  4. ^ a b "David L. Applegate", Recognizing Excellence: Award Recipients, Institute for Operations Research and the Management Sciences, retrieved 2017-08-03
  5. ^ a b The IEEE Communications Society William R. Bennett Prize, retrieved 2017-08-03
  6. ^ 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, archived from the original on December 20, 2013, 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
  8. ^ Peterson, Ivars (2002), Mathematical Treks: From Surreal Numbers to Magic Circles, MAA Spectrum, Mathematical Association of America, p. 71, ISBN 9780883855379
  9. ^ Lenstra, Jan Karel; Shmoys, David (2009), "The traveling salesman problem: a computational study", SIAM Review, 51 (4): 799–801, MR 2573947

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.