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. He is a recipient of Brown University's Philip J. Bray Award for Excellence in Teaching in the Sciences and was a Fellow at the Radcliffe Institute for Advanced Study at Harvard University. 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 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.

Klein has published two textbooks:
*