Philip N. Klein

131 papers A* 43A 5B 12Journal 58Unranked 11

Year	Rank	Type	Title / Venue / Authors
2023	J	`jnl`	Correlation Clustering and Two-Edge-Connected Augmentation for Planar Graphs. Algorithmica Philip N. Klein, Claire Mathieu, Hang Zhou
2021	J	`jnl`	A Quasipolynomial (2+ε)-Approximation for Planar Sparsest Cut. CoRR Vincent Cohen-Addad, Anupam Gupta, Philip N. Klein, Jason Li
2021	A*	`conf`	A quasipolynomial (2 + STOC Vincent Cohen-Addad, Anupam Gupta, Philip N. Klein, Jason Li
2021	—	`conf`	On the Computational Tractability of a Geographic Clustering Problem Arising in Redistricting. FORC Vincent Cohen-Addad, Philip N. Klein, Dániel Marx, Archer Wheeler, Christopher Wolfram
2020	J	`jnl`	New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut. CoRR Amir Abboud, Vincent Cohen-Addad, Philip N. Klein
2020	A*	`conf`	New hardness results for planar graph problems in p and an algorithm for sparsest cut. STOC Amir Abboud, Vincent Cohen-Addad, Philip N. Klein
2020	A*	`conf`	On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs. FOCS Vincent Cohen-Addad, Arnold Filtser, Philip N. Klein, Hung Le
2020	J	`jnl`	On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs. CoRR Vincent Cohen-Addad, Arnold Filtser, Philip N. Klein, Hung Le
2020	J	`jnl`	On the computational tractability of a geographic clustering problem arising in redistricting. CoRR Vincent Cohen-Addad, Philip N. Klein, Dániel Marx
2020	—	`conf`	The impact of highly compact algorithmic redistricting on the rural-versus-urban balance. SIGSPATIAL/GIS Archer Wheeler, Philip N. Klein
2019	B	`conf`	A PTAS for Bounded-Capacity Vehicle Routing in Planar Graphs. WADS Amariah Becker, Philip N. Klein, Aaron Schild
2019	J	`jnl`	A PTAS for Bounded-Capacity Vehicle Routing in Planar Graphs. CoRR Amariah Becker, Philip N. Klein, Aaron Schild
2019	J	`jnl`	A near-linear time minimum Steiner cut algorithm for planar graphs. CoRR Stephen Jue, Philip N. Klein
2019	A*	`conf`	Embedding Planar Graphs into Low-Treewidth Graphs with Applications to Efficient Approximation Schemes for Metric Problems. SODA Eli Fox-Epstein, Philip N. Klein, Aaron Schild
2019	J	`jnl`	Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics. SIAM J. Comput. Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu
2018	—	`conf`	Balanced centroidal power diagrams for redistricting. SIGSPATIAL/GIS Vincent Cohen-Addad, Philip N. Klein, Neal E. Young
2018	A	`conf`	Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension. ESA Amariah Becker, Philip N. Klein, David Saulpic
2017	A	`conf`	A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs. ESA Amariah Becker, Philip N. Klein, David Saulpic
2017	J	`jnl`	Balanced power diagrams for redistricting. CoRR Vincent Cohen-Addad, Philip N. Klein, Neal E. Young
2017	B	`conf`	Engineering an Approximation Scheme for Traveling Salesman in Planar Graphs. SEA Amariah Becker, Eli Fox-Epstein, Philip N. Klein, David Meierfrankenfeld
2017	J	`jnl`	Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time. SIAM J. Comput. Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, Christian Wulff-Nilsen
2017	J	`jnl`	Polynomial-Time Approximation Schemes for k-Center and Bounded-Capacity Vehicle Routing in Metrics with Bounded Highway Dimension. CoRR Amariah Becker, Philip N. Klein, David Saulpic
2017	A*	`ed.`	Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19 SODA Philip N. Klein
2016	J	`jnl`	Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 16221). Dagstuhl Reports Jeff Erickson, Philip N. Klein, Dániel Marx, Claire Mathieu
2016	A*	`conf`	Approximating connectivity domination in weighted bounded-genus graphs. STOC Vincent Cohen-Addad, Éric Colin de Verdière, Philip N. Klein, Claire Mathieu, David Meierfrankenfeld
2016	A*	`conf`	Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics. FOCS Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu
2016	J	`jnl`	The Two-Edge Connectivity Survivable-Network Design Problem in Planar Graphs. ACM Trans. Algorithms Glencora Borradaile, Philip N. Klein
2016	J	`jnl`	The power of local search for clustering. CoRR Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu
2015	J	`jnl`	A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest. ACM Trans. Algorithms Glencora Borradaile, Philip N. Klein, Claire Mathieu
2015	A*	`conf`	A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection. STOC Kyle Fox, Philip N. Klein, Shay Mozes
2015	J	`jnl`	A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection. CoRR Kyle Fox, Philip N. Klein, Shay Mozes
2015	A	`conf`	Correlation Clustering and Two-edge-connected Augmentation for Planar Graphs. STACS Philip N. Klein, Claire Mathieu, Hang Zhou
2015	J	`jnl`	On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms. SIAM J. Comput. Philip N. Klein, Neal E. Young
2014	—	`book`	A Cryptography Primer: Secrets and Promises Philip N. Klein
2014	A*	`conf`	A subexponential parameterized algorithm for Subset TSP on planar graphs. SODA Philip N. Klein, Dániel Marx
2014	A*	`conf`	Approximating SODA David Eisenstat, Philip N. Klein, Claire Mathieu
2014	J	`jnl`	Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs. ACM Trans. Algorithms Erik D. Demaine, Mohammad Taghi Hajiaghayi, Philip N. Klein
2013	J	`jnl`	A polynomial-time approximation scheme for Euclidean Steiner forest CoRR Glencora Borradaile, Philip N. Klein, Claire Mathieu
2013	J	`jnl`	Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 13421). Dagstuhl Reports Glencora Borradaile, Philip N. Klein, Dániel Marx, Claire Mathieu
2013	A*	`conf`	Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs. STOC David Eisenstat, Philip N. Klein
2013	A*	`conf`	Structured recursive separator decompositions for planar graphs in linear time. STOC Philip N. Klein, Shay Mozes, Christian Sommer
2013	J	`jnl`	The two-edge connectivity survivable-network design problem in planar graphs CoRR Glencora Borradaile, Philip N. Klein
2012	A*	`conf`	A polynomial-time approximation scheme for planar multiway cut. SODA MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Philip N. Klein, Claire Mathieu
2012	A*	`conf`	An efficient polynomial-time approximation scheme for Steiner forest in planar graphs. SODA David Eisenstat, Philip N. Klein, Claire Mathieu
2012	—	`conf`	Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time. ICALP (1) Philip N. Klein, Dániel Marx
2012	J	`jnl`	Structured Recursive Separator Decompositions for Planar Graphs in Linear Time CoRR Philip N. Klein, Shay Mozes, Christian Sommer
2011	J	`jnl`	An efficient polynomial-time approximation scheme for Steiner forest in planar graphs CoRR David Eisenstat, Philip N. Klein, Claire Mathieu
2011	—	`conf`	Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs. ICALP (1) Ken-ichi Kawarabayashi, Philip N. Klein, Christian Sommer
2011	J	`jnl`	Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus, and Minor-Free Graphs CoRR Ken-ichi Kawarabayashi, Philip N. Klein, Christian Sommer
2011	J	`jnl`	Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time CoRR Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, Christian Wulff-Nilsen
2011	A*	`conf`	Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time. FOCS Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, Christian Wulff-Nilsen
2011	B	`conf`	Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter · n log n) Time. WADS Philip N. Klein, Shay Mozes
2011	J	`jnl`	Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameternlog(n)) Time CoRR Philip N. Klein, Shay Mozes
2010	J	`jnl`	Multiple-source single-sink maximum flow in directed planar graphs in $O(n^{1.5} \log n)$ time CoRR Philip N. Klein, Shay Mozes
2010	J	`jnl`	Shortest paths in directed planar graphs with negative lengths: A linear-space ACM Trans. Algorithms Philip N. Klein, Shay Mozes, Oren Weimann
2009	J	`jnl`	An J. ACM Glencora Borradaile, Philip N. Klein
2009	J	`jnl`	An ACM Trans. Algorithms Glencora Borradaile, Philip N. Klein, Claire Mathieu
2009	—	`conf`	Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs. ICALP (1) Erik D. Demaine, MohammadTaghi Hajiaghayi, Philip N. Klein
2009	A*	`conf`	Shortest paths in directed planar graphs with negative lengths: a linear-space SODA Philip N. Klein, Shay Mozes, Oren Weimann
2008	J	`jnl`	A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights. SIAM J. Comput. Philip N. Klein
2008	A*	`conf`	A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest. FOCS Glencora Borradaile, Philip N. Klein, Claire Mathieu
2008	—	`conf`	The Two-Edge Connectivity Survivable Network Problem in Planar Graphs. ICALP (1) Glencora Borradaile, Philip N. Klein
2007	A*	`conf`	A polynomial-time approximation scheme for Steiner tree in planar graphs. SODA Glencora Borradaile, Claire Kenyon-Mathieu, Philip N. Klein
2007	B	`conf`	Steiner Tree in Planar Graphs: An WADS Glencora Borradaile, Philip N. Klein, Claire Mathieu
2006	A*	`conf`	A subset spanner for Planar graphs, : with application to subset TSP. STOC Philip N. Klein
2006	A*	`conf`	An SODA Glencora Borradaile, Philip N. Klein
2005	A*	`conf`	A linear-time approximation scheme for planar weighted TSP. FOCS Philip N. Klein
2005	A*	`conf`	Multiple-source shortest paths in planar graphs. SODA Philip N. Klein
2004	J	`jnl`	Approximation algorithms for finding low-degree subgraphs. Networks Philip N. Klein, Radha Krishnan, Balaji Raghavachari, R. Ravi
2004	J	`jnl`	Recognition of Shapes by Editing Their Shock Graphs. IEEE Trans. Pattern Anal. Mach. Intell. Thomas B. Sebastian, Philip N. Klein, Benjamin B. Kimia
2004	J	`jnl`	Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut. Math. Oper. Res. David R. Karger, Philip N. Klein, Clifford Stein, Mikkel Thorup, Neal E. Young
2003	J	`jnl`	Detecting Race Conditions in Parallel Programs that Use Semaphores. Algorithmica Philip N. Klein, Robert H. B. Netzer, Hsueh-I Lu
2003	J	`jnl`	On Aligning Curves. IEEE Trans. Pattern Anal. Mach. Intell. Thomas B. Sebastian, Philip N. Klein, Benjamin B. Kimia
2002	J	`jnl`	Detecting Race Conditions in Parallel Programs that Use Semaphores CoRR Philip N. Klein, Hsueh-I Lu, Robert H. B. Netzer
2002	J	`jnl`	On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms CoRR Philip N. Klein, Neal E. Young
2002	A*	`conf`	Preprocessing an undirected planar network to enable fast approximate distance queries. SODA Philip N. Klein
2002	J	`jnl`	Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut CoRR David R. Karger, Philip N. Klein, Clifford Stein, Mikkel Thorup, Neal E. Young
2002	—	`conf`	Shock-Based Indexing into Large Shape Databases. ECCV (3) Thomas B. Sebastian, Philip N. Klein, Benjamin B. Kimia
2001	—	`conf`	Alignment-Based Recognition of Shape Outlines. IWVF Thomas B. Sebastian, Philip N. Klein, Benjamin B. Kimia
2001	A*	`conf`	Recognition of Shapes by Editing Shock Graphs. ICCV Thomas B. Sebastian, Philip N. Klein, Benjamin B. Kimia
2001	A*	`conf`	Shape matching using edit-distance: an implementation. SODA Philip N. Klein, Thomas B. Sebastian, Benjamin B. Kimia
2000	A*	`conf`	A tree-edit-distance algorithm for comparing simple, closed shapes. SODA Philip N. Klein, Srikanta Tirthapura, Daniel Sharvit, Benjamin B. Kimia
2000	A*	`conf`	Finding the closest lattice vector when it's unusually close. SODA Philip N. Klein
2000	A*	`conf`	Using router stamping to identify the source of IP packets. CCS Thomas W. Doeppner Jr., Philip N. Klein, Andrew Koyfman
1999	—	`ch.`	Approximation Algorithms. Algorithms and Theory of Computation Handbook Philip N. Klein, Neal E. Young
1999	B	`conf`	On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms. IPCO Philip N. Klein, Neal E. Young
1999	A*	`conf`	Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut. STOC David R. Karger, Philip N. Klein, Clifford Stein, Mikkel Thorup, Neal E. Young
1998	J	`jnl`	A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs. Algorithmica Philip N. Klein, Sairam Subramanian
1998	A*	`conf`	A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP. SODA Sanjeev Arora, Michelangelo Grigni, David R. Karger, Philip N. Klein, Andrzej Woloszyn
1998	A	`conf`	Computing the Edit-Distance between Unrooted Ordered Trees. ESA Philip N. Klein
1998	B	`conf`	Space-Efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programs. ISAAC Philip N. Klein, Hsueh-I Lu
1997	J	`jnl`	A Randomized Parallel Algorithm for Single-Source Shortest Paths. J. Algorithms Philip N. Klein, Sairam Subramanian
1997	J	`jnl`	Approximation Algorithms for Steiner and Directed Multicuts. J. Algorithms Philip N. Klein, Serge A. Plotkin, Satish Rao, Éva Tardos
1997	J	`jnl`	Faster Shortest-Path Algorithms for Planar Graphs. J. Comput. Syst. Sci. Monika Rauch Henzinger, Philip N. Klein, Satish Rao, Sairam Subramanian
1996	A*	`conf`	Efficient Approximation Algorithms for Semidefinite Programs Arising from MAX CUT and COLORING. STOC Philip N. Klein, Hsueh-I Lu
1996	J	`jnl`	Efficient Parallel Algorithms for Chordal Graphs. SIAM J. Comput. Philip N. Klein
1996	B	`conf`	Finding Minimum Spanning Forests in Logarithmic Time and Linear Work Using Random Sampling. SPAA Richard Cole, Philip N. Klein, Robert Endre Tarjan
1996	A	`conf`	Race-Condition Detection in Parallel Computation with Semaphores (Extended Abstract). ESA Philip N. Klein, Hsueh-I Lu, Robert H. B. Netzer
1995	J	`jnl`	A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees. J. Algorithms Philip N. Klein, R. Ravi
1995	J	`jnl`	A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees. J. ACM David R. Karger, Philip N. Klein, Robert Endre Tarjan
1995	J	`jnl`	An Approximate Max-Flow Min-Cut Relation for Unidirected Multicommodity Flow, with Applications. Comb. Philip N. Klein, Satish Rao, Ajit Agrawal, R. Ravi
1995	J	`jnl`	When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks. SIAM J. Comput. Ajit Agrawal, Philip N. Klein, R. Ravi
1994	J	`jnl`	A Data Structure for Bicategories, with Application to Speeding up an Approximation Algorithm. Inf. Process. Lett. Philip N. Klein
1994	A*	`conf`	A randomized linear-time algorithm for finding minimum spanning trees. STOC Philip N. Klein, Robert Endre Tarjan
1994	J	`jnl`	Faster Approximation Algorithms for the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts. SIAM J. Comput. Philip N. Klein, Serge A. Plotkin, Clifford Stein, Éva Tardos
1994	A*	`conf`	Faster shortest-path algorithms for planar graphs. STOC Philip N. Klein, Satish Rao, Monika Rauch, Sairam Subramanian
1993	B	`conf`	A Fully Dynamic Approximation Scheme for All-Pairs Shortest Paths in Planar Graphs. WADS Philip N. Klein, Sairam Subramanian
1993	J	`jnl`	A Parallel Algorithm for Approximating the Minimum Cycle Cover. Algorithmica Philip N. Klein, Clifford Stein
1993	A*	`conf`	A linear-processor polylog-time algorithm for shortest paths in planar graphs FOCS Philip N. Klein, Sairam Subramanian
1993	B	`conf`	A nearly best-possible approximation algorithm for node-weighted Steiner trees. IPCO Philip N. Klein, R. Ravi
1993	B	`conf`	Detecting Race Conditions in Parallel Programs that Use One Semaphore. WADS Hsueh-I Lu, Philip N. Klein, Robert H. B. Netzer
1993	A*	`conf`	Excluded minors, network decomposition, and multicommodity flow. STOC Philip N. Klein, Serge A. Plotkin, Satish Rao
1993	B	`conf`	On Gazit and Miller's Parallel Algorithm for Planar Separators: Achieving Greater Efficiency Through Random Sampling. SPAA Philip N. Klein
1993	J	`jnl`	Parallelism, Preprocessing, and Reachability: A Hybrid Algorithm for Directed Graphs. J. Algorithms Philip N. Klein
1993	J	`jnl`	The Lattice Structure of Flow in Planar Graphs. SIAM J. Discret. Math. Samir Khuller, Joseph Naor, Philip N. Klein
1993	J	`jnl`	Towards Overcoming the Transitive-Closure Bottleneck: Efficient Parallel Algorithms for Planar Digraphs. J. Comput. Syst. Sci. Ming-Yang Kao, Philip N. Klein
1993	B	`conf`	When cycles collapse: A general approximation technique for constrained two-connectivity problems. IPCO Philip N. Klein, R. Ravi
1992	A*	`conf`	A Parallel Randomized Approximation Scheme for Shortest Paths STOC Philip N. Klein, Sairam Sairam
1992	—	`conf`	Approximation Through Local Optimality: Designing Networks with Small Degree. FSTTCS R. Ravi, Balaji Raghavachari, Philip N. Klein
1991	—	`conf`	Approximating Concurrent Flow with Unit Demands and Capacities: An Implementation. Network Flows And Matching James M. Borger, Sarah Kang, Philip N. Klein
1991	A*	`conf`	Ordering Problems Approximated: Single-Processor Scheduling and Interval Graph Completion. ICALP R. Ravi, Ajit Agrawal, Philip N. Klein
1991	A*	`conf`	When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks STOC Ajit Agrawal, Philip N. Klein, R. Ravi
1990	J	`jnl`	A Parallel Algorithm for Eliminating Cycles in Undirected Graphs. Inf. Process. Lett. Philip N. Klein, Clifford Stein
1990	A*	`conf`	Approximation through Multicommodity Flow FOCS Philip N. Klein, Ajit Agrawal, R. Ravi, Satish Rao
1990	A*	`conf`	Leighton-Rao Might Be Practical: Faster Approximation Algorithms for Concurrent Flow with Uniform Capacities STOC Philip N. Klein, Clifford Stein, Éva Tardos
1990	J	`jnl`	On the Time-Space Complexity of Reachability Queries for Preprocessed Graphs. Inf. Process. Lett. Lisa Hellerstein, Philip N. Klein, Robert Wilber
1990	A*	`conf`	Towards Overcoming the Transitive-Closure Bottleneck: Efficient Parallel Algorithms for Planar Digraphs STOC Ming-Yang Kao, Philip N. Klein
1988	J	`jnl`	An Efficient Parallel Algorithm for Planarity. J. Comput. Syst. Sci. Philip N. Klein, John H. Reif
1988	A*	`conf`	Efficient Parallel Algorithms for Chordal Graphs FOCS Philip N. Klein
1988	J	`jnl`	Parallel Time O(log n) Acceptance of Deterministic CFLs on an Exclusive-Write P-RAM. SIAM J. Comput. Philip N. Klein, John H. Reif
1986	A*	`conf`	An Efficient Parallel Algorithm for Planarity FOCS Philip N. Klein, John H. Reif