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).

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 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: