Philip N. Klein
Philip N. Klein is an American computer scientist and 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). 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.
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".[2][3][4]
- 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.[5][6][7]
- In 2005, Klein gave a linear-time algorithm to find a nearly optimal traveling salesman tour in a planar graph.[8][9]
Books
Klein has published two textbooks:
- A Cryptography Primer: Secrets and Promises[10]
- Coding the Matrix: Linear Algebra through Computer Science Applications[11]
References
- ↑ "Philip N Klein". awards.acm.org. Retrieved 2022-05-29.
- ↑ 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. 24 (3): 440–456. doi: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.
- ↑ Hochbaum, Dorit. Approximation Algorithms for NP-Hard Problems. p. 158. Search this book on
- ↑ Motwani, Rajeev; Raghavan, Prabhakar (1995). Randomized Algorithms. Cambridge University Press. pp. Section 10.3. Search this book on
- ↑ Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995). "A randomized linear-time algorithm to find minimum spanning trees". Journal of the ACM (JACM) 42. 42 (2): 321–328. doi:10.1145/201019.201022. Unknown parameter
|s2cid=ignored (help) - ↑ Klein, Philip N.; Tarjan, Robert E. (1994). "A randomized linear-time algorithm for finding minimum spanning trees". Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing: 9–15. doi:10.1145/195058.195084. ISBN 0897916638. Unknown parameter
|s2cid=ignored (help) - ↑ Klein, Philip N. (2008). "A linear-time approximation scheme for TSP in undirected planar graphs with edge-weights". SIAM Journal on Computing 37. 37 (6): 1926–1952. doi:10.1137/060649562.
- ↑ Klein, Philip N. (2005). "A linear-time approximation scheme for planar weighted TSP". Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science: 647–656. doi:10.1109/SFCS.2005.7. ISBN 0-7695-2468-0. Unknown parameter
|s2cid=ignored (help) - ↑ Klein, Philip (2014). A Cryptography Primer: Secrets and Promises. Cambridge University Press. Search this book on
- ↑ Klein, Philip (2013). Coding the Matrix: Linear Algebra through Computer Science Applications. Newtonian Press. Search this book on
This article "Philip N. Klein" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Philip N. Klein. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
|
This page exists already on Wikipedia. |
