 |
Philip Klein
Professor of Computer ScienceContact Information
Box 1910Brown University
Providence, RI 02912
Email: klein at cs.brown.edu
Personal home page: http://www.cs.brown.edu/~klein/
Research Areas
| Combinatorial Optimization |
| Design and Analysis of Algorithms |
| Theory of Computation |
Research Topics or Projects
Courses Taught
Research Interests
Philip Klein does research in algorithms and data structures, especially in the area of combinatorial optimization, and especially those problems involving graphs.
Past work includes approximation algorithms (including the development of the primal-dual method for the Steiner forest problem), randomized algorithms (including the first linear-time algorithm for finding minimum-cost spanning trees), and parallel algorithms (including the first linear-processor, polylog-time algorithms for fundamental problems in planar graphs, e.g. topological sorting and shortest paths).
Some recent work motivated by computer vision focuses on algorithms for comparing pairs of geometric structures, primarily curves and two-dimensional shapes, by computing the minimum cost required to transform one to the other. This work furthers the goal of developing a content-addressable database of shapes. Other recent work addresses optimization problems in planar graphs, such as finding an approximately minimum-cost Traveling Salesperson tour in an undirected planar graph and finding a maximum st-flow in a directed planar graph.
Selected Publications
Borradaile, G., and Klein, P. N. An O(n log n) algorithm for maximum st-flow in a directed planar graph. In Symposium on Discrete Algorithms (2006), pp. 524-533. [ pdf ]
Klein, P. N. A subset spanner for planar graphs, with application to subset TSP. In Proceedings of the Thirty-Eighth ACM Symposium on Theory of Computing (2006), pp. 524-533. [ pdf ]
Klein, P. N. A linear-time approximation scheme for TSP for planar weighted graphs. In Proceedings of the Forty-Sixth IEEE Symposium on Foundations of Computer Science (2005), pp. 647-656. [ pdf ]
Klein, P. N. Multiple-source shortest paths in planar graphs. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (2005), pp. 146-155. [ pdf ]
Karger, D. R., Klein, P., Stein, C., Thorup, M., and Young, N. E. Rounding algorithms for a geometric embedding of minimum multiway cut. Mathematics of Operations Research 29, 3 (2004), 436-461. [ pdf ]
Klein, P. N. Preprocessing an undirected planar network to enable fast. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium On Discrete Mathematics (2002), pp. 820-827. [ pdf ]
Klein, P. N. Finding the closest lattice vector when it's unusually close. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (2000), pp. 937-941. [ pdf ]
Henzinger, M. R., Klein, P. N., Rao, S., and Subramanian, S. Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences 55, 1 (1997), 3-23. [ pdf ]
Agrawal, A., Klein, P. N., and Ravi, R. When trees collide: An approximation algorithm for the generalized Steiner tree problem on networks. SIAM Journal on Computing 24 (1995), 440-456. [ pdf ]
Karger, D. R., Klein, P. N., and Tarjan, R. E. A randomized linear-time algorithm to find minimum spanning trees. Journal of the ACM 42 (1995), 321-328. [ pdf ]
All publications by Philip Klein
| Page Owner: Philip Klein | Last Modified: Mon Aug 20 14:30:39 2007 |