Philip N. Klein Explained
Philip N. Klein is an American computer scientist and professor at Brown University. His research focuses on algorithms for optimization problems in graphs.
Klein is a fellow of the Association for Computing Machinery[1] and a recipient of the National Science Foundation's Presidential Young Investigator Award (1991).[2] He is a recipient of Brown University's Philip J. Bray Award for Excellence in Teaching in the Sciences (2007) and was a Fellow at the Radcliffe Institute for Advanced Study at Harvard University (2015–16). He graduated summa cum laude from Harvard with an A.B. in Applied Mathematics and earned a Ph.D. in Computer Science at MIT.[3]
Key contributions
- In 1991, Klein and his then-students Ajit Agrawal and R. Ravi gave an approximation algorithm for network design that is considered "the first highly sophisticated use of the primal-dual method in the design of approximation algorithms". In 2023, this research received the Annual ACM Symposium on Theory of Computing (STOC) 30-year Test of Time Award.[4] [5] [6] [7]
- In 1994, Klein and Robert E. Tarjan gave a randomized linear-time algorithm to find minimum spanning trees, based on a sampling technique due to David Karger.[8] [9] [10]
- In 2005, Klein gave a linear-time algorithm to find a nearly optimal traveling salesman tour in a planar graph.[11] [12]
Books
Klein has published two textbooks:
Notes and References
- Web site: Philip N Klein . 2022-05-29 . awards.acm.org . en.
- Web site: Philip N. Klein . live . https://web.archive.org/web/20220103024017/http://cs.brown.edu/people/pklein/ . 2022-01-03 . 2022-06-27 . cs.brown.edu.
- Web site: Philip N. Klein . live . https://web.archive.org/web/20220419133808/https://www.radcliffe.harvard.edu/people/philip-n-klein . 2022-04-19 . 2022-06-27 . Radcliffe Institute for Advanced Study at Harvard University . en.
- Web site: Philip Klein And Brown CS Alums Receive The 2023 STOC Test Of Time Award .
- Agrawal . Ajit . Klein . Philip . Ravi . R. . 1995 . When trees collide: An approximation algorithm for the generalized Steiner problem on networks . SIAM Journal on Computing . 24 . 3 . 440–456. 10.1137/S0097539792236237 .
- Agrawal . Ajit . Klein . Philip . Ravi . R. . 1991 . "When trees collide: An approximation algorithm for the generalized Steiner problem on networks" . Proceedings of the 23rd Annual ACM Symposium on Theory of Computing . 134–144.
- Book: Hochbaum, Dorit . Approximation Algorithms for NP-Hard Problems . 158.
- Book: Motwani . Rajeev . Randomized Algorithms . Raghavan . Prabhakar . Cambridge University Press . 1995 . Section 10.3.
- Karger . David R. . Klein . Philip N. . Tarjan . Robert E. . 1995 . A randomized linear-time algorithm to find minimum spanning trees . Journal of the ACM . 42 . 2 . 321–328. 10.1145/201019.201022 . 832583 . free .
- Book: Klein . Philip N. . Tarjan . Robert E. . Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 . A randomized linear-time algorithm for finding minimum spanning trees . 1994 . 9–15. 10.1145/195058.195084 . 0897916638 . 15667728 .
- Klein . Philip N. . 2008 . A linear-time approximation scheme for TSP in undirected planar graphs with edge-weights . SIAM Journal on Computing . 37 . 6 . 1926–1952. 10.1137/060649562 . 10.1.1.155.897 .
- Book: Klein, Philip N. . 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05) . A linear-time approximation scheme for planar weighted TSP . 2005 . 647–656. 10.1109/SFCS.2005.7 . 0-7695-2468-0 . 16327107 .
- Book: Klein, Philip N. . A cryptography primer : secrets and promises . 2014 . 978-1-107-01788-7 . New York, NY, USA . 863632974.
- Book: Klein, Philip N. . Coding the matrix : linear algebra through applications to computer science . 2013 . 978-0-615-85673-5 . Newtonian Press . [Newton, Mass.] . 855087626.
