Philip N. Klein

Publication Activity (10 Years)

Years Active: 1986-2023
Publications (10 Years): 32

Top Venues

CoRR

STOC

SODA

ACM Trans. Algorithms

Publications

Philip N. Klein, Claire Mathieu, Hang Zhou
Correlation Clustering and Two-Edge-Connected Augmentation for Planar Graphs. Algorithmica 85 (10) (2023)
Vincent Cohen-Addad, Philip N. Klein, Dániel Marx, Archer Wheeler, Christopher Wolfram
On the Computational Tractability of a Geographic Clustering Problem Arising in Redistricting. FORC (2021)
Vincent Cohen-Addad, Anupam Gupta, Philip N. Klein, Jason Li
)-approximation for planar sparsest cut. STOC (2021)
Vincent Cohen-Addad, Anupam Gupta, Philip N. Klein, Jason Li
A Quasipolynomial (2+ε)-Approximation for Planar Sparsest Cut. CoRR (2021)
Vincent Cohen-Addad, Arnold Filtser, Philip N. Klein, Hung Le
On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs. CoRR (2020)
Amir Abboud, Vincent Cohen-Addad, Philip N. Klein
New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut. CoRR (2020)
Amir Abboud, Vincent Cohen-Addad, Philip N. Klein
New hardness results for planar graph problems in p and an algorithm for sparsest cut. STOC (2020)
Archer Wheeler, Philip N. Klein
The impact of highly compact algorithmic redistricting on the rural-versus-urban balance. SIGSPATIAL/GIS (2020)
Vincent Cohen-Addad, Philip N. Klein, Dániel Marx
On the computational tractability of a geographic clustering problem arising in redistricting. CoRR (2020)
Vincent Cohen-Addad, Arnold Filtser, Philip N. Klein, Hung Le
On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs. FOCS (2020)
Stephen Jue, Philip N. Klein
A near-linear time minimum Steiner cut algorithm for planar graphs. CoRR (2019)
Amariah Becker, Philip N. Klein, Aaron Schild
A PTAS for Bounded-Capacity Vehicle Routing in Planar Graphs. CoRR (2019)
Amariah Becker, Philip N. Klein, Aaron Schild
A PTAS for Bounded-Capacity Vehicle Routing in Planar Graphs. WADS (2019)
Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu
Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics. SIAM J. Comput. 48 (2) (2019)
Eli Fox-Epstein, Philip N. Klein, Aaron Schild
Embedding Planar Graphs into Low-Treewidth Graphs with Applications to Efficient Approximation Schemes for Metric Problems. SODA (2019)
Vincent Cohen-Addad, Philip N. Klein, Neal E. Young
Balanced centroidal power diagrams for redistricting. SIGSPATIAL/GIS (2018)
Amariah Becker, Philip N. Klein, David Saulpic
Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension. ESA (2018)
Amariah Becker, Philip N. Klein, David Saulpic
A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs. ESA (2017)
Amariah Becker, Philip N. Klein, David Saulpic
Polynomial-Time Approximation Schemes for k-Center and Bounded-Capacity Vehicle Routing in Metrics with Bounded Highway Dimension. CoRR (2017)
Vincent Cohen-Addad, Philip N. Klein, Neal E. Young
Balanced power diagrams for redistricting. CoRR (2017)
Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, Christian Wulff-Nilsen
Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time. SIAM J. Comput. 46 (4) (2017)
Amariah Becker, Eli Fox-Epstein, Philip N. Klein, David Meierfrankenfeld
Engineering an Approximation Scheme for Traveling Salesman in Planar Graphs. SEA (2017)
Glencora Borradaile, Philip N. Klein
The Two-Edge Connectivity Survivable-Network Design Problem in Planar Graphs. ACM Trans. Algorithms 12 (3) (2016)
Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu
The power of local search for clustering. CoRR (2016)
Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu
Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics. FOCS (2016)
Jeff Erickson, Philip N. Klein, Dániel Marx, Claire Mathieu
Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 16221). Dagstuhl Reports 6 (5) (2016)
Vincent Cohen-Addad, Éric Colin de Verdière, Philip N. Klein, Claire Mathieu, David Meierfrankenfeld
Approximating connectivity domination in weighted bounded-genus graphs. STOC (2016)
Glencora Borradaile, Philip N. Klein, Claire Mathieu
A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest. ACM Trans. Algorithms 11 (3) (2015)
Kyle Fox, Philip N. Klein, Shay Mozes
A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection. STOC (2015)
Kyle Fox, Philip N. Klein, Shay Mozes
A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection. CoRR (2015)
Philip N. Klein, Neal E. Young
On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms. SIAM J. Comput. 44 (4) (2015)
Philip N. Klein, Claire Mathieu, Hang Zhou
Correlation Clustering and Two-edge-connected Augmentation for Planar Graphs. STACS (2015)
David Eisenstat, Philip N. Klein, Claire Mathieu
-center in planar graphs. SODA (2014)
Philip N. Klein, Dániel Marx
A subexponential parameterized algorithm for Subset TSP on planar graphs. SODA (2014)
Erik D. Demaine, Mohammad Taghi Hajiaghayi, Philip N. Klein
Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs. ACM Trans. Algorithms 10 (3) (2014)
Glencora Borradaile, Philip N. Klein
The two-edge connectivity survivable-network design problem in planar graphs CoRR (2013)
Philip N. Klein, Shay Mozes, Christian Sommer
Structured recursive separator decompositions for planar graphs in linear time. STOC (2013)
Glencora Borradaile, Philip N. Klein, Claire Mathieu
A polynomial-time approximation scheme for Euclidean Steiner forest CoRR (2013)
David Eisenstat, Philip N. Klein
Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs. STOC (2013)
Glencora Borradaile, Philip N. Klein, Dániel Marx, Claire Mathieu
Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 13421). Dagstuhl Reports 3 (10) (2013)
Philip N. Klein, Dániel Marx
Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time. ICALP (1) (2012)
MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Philip N. Klein, Claire Mathieu
A polynomial-time approximation scheme for planar multiway cut. SODA (2012)
David Eisenstat, Philip N. Klein, Claire Mathieu
An efficient polynomial-time approximation scheme for Steiner forest in planar graphs. SODA (2012)
Philip N. Klein, Shay Mozes, Christian Sommer
Structured Recursive Separator Decompositions for Planar Graphs in Linear Time CoRR (2012)
Philip N. Klein, Shay Mozes
Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter*n*log(n)) Time CoRR (2011)
Philip N. Klein, Shay Mozes
Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter · n log n) Time. WADS (2011)
David Eisenstat, Philip N. Klein, Claire Mathieu
An efficient polynomial-time approximation scheme for Steiner forest in planar graphs CoRR (2011)
Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, Christian Wulff-Nilsen
Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time CoRR (2011)
Ken-ichi Kawarabayashi, Philip N. Klein, Christian Sommer
Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus, and Minor-Free Graphs CoRR (2011)
Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, Christian Wulff-Nilsen
Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time. FOCS (2011)
Ken-ichi Kawarabayashi, Philip N. Klein, Christian Sommer
Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs. ICALP (1) (2011)
Philip N. Klein, Shay Mozes, Oren Weimann
)-time algorithm. ACM Trans. Algorithms 6 (2) (2010)
Philip N. Klein, Shay Mozes
Multiple-source single-sink maximum flow in directed planar graphs in $O(n^{1.5} \log n)$ time CoRR (2010)
Glencora Borradaile, Philip N. Klein
-flow in a directed planar graph. J. ACM 56 (2) (2009)
Erik D. Demaine, MohammadTaghi Hajiaghayi, Philip N. Klein
Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs. ICALP (1) (2009)
Glencora Borradaile, Philip N. Klein, Claire Mathieu
) approximation scheme for Steiner tree in planar graphs. ACM Trans. Algorithms 5 (3) (2009)
Philip N. Klein, Shay Mozes, Oren Weimann
)-time algorithm. SODA (2009)
Glencora Borradaile, Philip N. Klein
The Two-Edge Connectivity Survivable Network Problem in Planar Graphs. ICALP (1) (2008)
Glencora Borradaile, Philip N. Klein, Claire Mathieu
A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest. FOCS (2008)
Philip N. Klein
A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights. SIAM J. Comput. 37 (6) (2008)
Glencora Borradaile, Claire Kenyon-Mathieu, Philip N. Klein
A polynomial-time approximation scheme for Steiner tree in planar graphs. SODA (2007)
Glencora Borradaile, Philip N. Klein, Claire Mathieu
) Approximation Scheme with Singly-Exponential Dependence on Epsilon. WADS (2007)
Glencora Borradaile, Philip N. Klein
-flow in a directed planar graph. SODA (2006)
Philip N. Klein
A subset spanner for Planar graphs, : with application to subset TSP. STOC (2006)
Philip N. Klein
A linear-time approximation scheme for planar weighted TSP. FOCS (2005)
Philip N. Klein
Multiple-source shortest paths in planar graphs. SODA (2005)
Thomas B. Sebastian, Philip N. Klein, Benjamin B. Kimia
Recognition of Shapes by Editing Their Shock Graphs. IEEE Trans. Pattern Anal. Mach. Intell. 26 (5) (2004)
David R. Karger, Philip N. Klein, Clifford Stein, Mikkel Thorup, Neal E. Young
Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut. Math. Oper. Res. 29 (3) (2004)
Philip N. Klein, Radha Krishnan, Balaji Raghavachari, R. Ravi
Approximation algorithms for finding low-degree subgraphs. Networks 44 (3) (2004)
Philip N. Klein, Robert H. B. Netzer, Hsueh-I Lu
Detecting Race Conditions in Parallel Programs that Use Semaphores. Algorithmica 35 (4) (2003)
Thomas B. Sebastian, Philip N. Klein, Benjamin B. Kimia
On Aligning Curves. IEEE Trans. Pattern Anal. Mach. Intell. 25 (1) (2003)
Thomas B. Sebastian, Philip N. Klein, Benjamin B. Kimia
Shock-Based Indexing into Large Shape Databases. ECCV (3) (2002)
David R. Karger, Philip N. Klein, Clifford Stein, Mikkel Thorup, Neal E. Young
Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut CoRR (2002)
Philip N. Klein, Hsueh-I Lu, Robert H. B. Netzer
Detecting Race Conditions in Parallel Programs that Use Semaphores CoRR (2002)
Philip N. Klein, Neal E. Young
On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms CoRR (2002)
Philip N. Klein
Preprocessing an undirected planar network to enable fast approximate distance queries. SODA (2002)
Philip N. Klein, Thomas B. Sebastian, Benjamin B. Kimia
Shape matching using edit-distance: an implementation. SODA (2001)
Thomas B. Sebastian, Philip N. Klein, Benjamin B. Kimia
Recognition of Shapes by Editing Shock Graphs. ICCV (2001)
Thomas B. Sebastian, Philip N. Klein, Benjamin B. Kimia
Alignment-Based Recognition of Shape Outlines. IWVF (2001)
Thomas W. Doeppner Jr., Philip N. Klein, Andrew Koyfman
Using router stamping to identify the source of IP packets. CCS (2000)
Philip N. Klein, Srikanta Tirthapura, Daniel Sharvit, Benjamin B. Kimia
A tree-edit-distance algorithm for comparing simple, closed shapes. SODA (2000)
Philip N. Klein
Finding the closest lattice vector when it's unusually close. SODA (2000)
Philip N. Klein, Neal E. Young
On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms. IPCO (1999)
David R. Karger, Philip N. Klein, Clifford Stein, Mikkel Thorup, Neal E. Young
Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut. STOC (1999)
Philip N. Klein, Hsueh-I Lu
Space-Efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programs. ISAAC (1998)
Philip N. Klein, Sairam Subramanian
A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs. Algorithmica 22 (3) (1998)
Sanjeev Arora, Michelangelo Grigni, David R. Karger, Philip N. Klein, Andrzej Woloszyn
A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP. SODA (1998)
Philip N. Klein
Computing the Edit-Distance between Unrooted Ordered Trees. ESA (1998)
Philip N. Klein, Serge A. Plotkin, Satish Rao, Éva Tardos
Approximation Algorithms for Steiner and Directed Multicuts. J. Algorithms 22 (2) (1997)
Monika Rauch Henzinger, Philip N. Klein, Satish Rao, Sairam Subramanian
Faster Shortest-Path Algorithms for Planar Graphs. J. Comput. Syst. Sci. 55 (1) (1997)
Philip N. Klein, Sairam Subramanian
A Randomized Parallel Algorithm for Single-Source Shortest Paths. J. Algorithms 25 (2) (1997)
Philip N. Klein
Efficient Parallel Algorithms for Chordal Graphs. SIAM J. Comput. 25 (4) (1996)
Richard Cole, Philip N. Klein, Robert Endre Tarjan
Finding Minimum Spanning Forests in Logarithmic Time and Linear Work Using Random Sampling. SPAA (1996)
Philip N. Klein, Hsueh-I Lu
Efficient Approximation Algorithms for Semidefinite Programs Arising from MAX CUT and COLORING. STOC (1996)
Philip N. Klein, Hsueh-I Lu, Robert H. B. Netzer
Race-Condition Detection in Parallel Computation with Semaphores (Extended Abstract). ESA (1996)
Ajit Agrawal, Philip N. Klein, R. Ravi
When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks. SIAM J. Comput. 24 (3) (1995)
Philip N. Klein, Satish Rao, Ajit Agrawal, R. Ravi
An Approximate Max-Flow Min-Cut Relation for Unidirected Multicommodity Flow, with Applications. Comb. 15 (2) (1995)
Philip N. Klein, R. Ravi
A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees. J. Algorithms 19 (1) (1995)
David R. Karger, Philip N. Klein, Robert Endre Tarjan
A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees. J. ACM 42 (2) (1995)
Philip N. Klein
A Data Structure for Bicategories, with Application to Speeding up an Approximation Algorithm. Inf. Process. Lett. 52 (6) (1994)

Philip N. Klein.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Philip N. Klein