Philip N. Klein

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 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". In 2023, this research received the Annual ACM Symposium on Theory of Computing (STOC) 30-year Test of Time Award.
• 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.
• In 2005, Klein gave a linear-time algorithm to find a nearly optimal traveling salesman tour in a planar graph.

Books

Klein has published two textbooks:

References