Philip N. Klein

According to our database, Philip N. Klein authored at least 102 papers between 1988 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2023

Correlation Clustering and Two-Edge-Connected Augmentation for Planar Graphs.

Philip N. Klein, Claire Mathieu, Hang Zhou

Algorithmica, October, 2023

2021

A Quasipolynomial (2+ε)-Approximation for Planar Sparsest Cut.

Vincent Cohen-Addad, Anupam Gupta, Philip N. Klein, Jason Li

CoRR, 2021

A quasipolynomial (2 + <i>ε</i>)-approximation for planar sparsest cut.

Vincent Cohen-Addad, Anupam Gupta, Philip N. Klein, Jason Li

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

On the Computational Tractability of a Geographic Clustering Problem Arising in Redistricting.

Vincent Cohen-Addad, Philip N. Klein, Dániel Marx, Archer Wheeler, Christopher Wolfram

Proceedings of the 2nd Symposium on Foundations of Responsible Computing, 2021

2020

On the computational tractability of a geographic clustering problem arising in redistricting.

Vincent Cohen-Addad, Philip N. Klein, Dániel Marx

CoRR, 2020

New hardness results for planar graph problems in p and an algorithm for sparsest cut.

Amir Abboud, Vincent Cohen-Addad, Philip N. Klein

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

The impact of highly compact algorithmic redistricting on the rural-versus-urban balance.

Archer Wheeler, Philip N. Klein

Proceedings of the SIGSPATIAL '20: 28th International Conference on Advances in Geographic Information Systems, 2020

On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs.

Vincent Cohen-Addad, Arnold Filtser, Philip N. Klein, Hung Le

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics.

Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu

SIAM J. Comput., 2019

A near-linear time minimum Steiner cut algorithm for planar graphs.

Stephen Jue, Philip N. Klein

CoRR, 2019

A PTAS for Bounded-Capacity Vehicle Routing in Planar Graphs.

Amariah Becker, Philip N. Klein, Aaron Schild

Proceedings of the Algorithms and Data Structures - 16th International Symposium, 2019

Embedding Planar Graphs into Low-Treewidth Graphs with Applications to Efficient Approximation Schemes for Metric Problems.

Eli Fox-Epstein, Philip N. Klein, Aaron Schild

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018

Balanced centroidal power diagrams for redistricting.

Vincent Cohen-Addad, Philip N. Klein, Neal E. Young

Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2018

Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension.

Amariah Becker, Philip N. Klein, David Saulpic

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

2017

Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time.

Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, Christian Wulff-Nilsen

SIAM J. Comput., 2017

Balanced power diagrams for redistricting.

Vincent Cohen-Addad, Philip N. Klein, Neal E. Young

CoRR, 2017

Polynomial-Time Approximation Schemes for k-Center and Bounded-Capacity Vehicle Routing in Metrics with Bounded Highway Dimension.

Amariah Becker, Philip N. Klein, David Saulpic

CoRR, 2017

Engineering an Approximation Scheme for Traveling Salesman in Planar Graphs.

Amariah Becker, Eli Fox-Epstein, Philip N. Klein, David Meierfrankenfeld

Proceedings of the 16th International Symposium on Experimental Algorithms, 2017

A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs.

Amariah Becker, Philip N. Klein, David Saulpic

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

2016

The Two-Edge Connectivity Survivable-Network Design Problem in Planar Graphs.

Glencora Borradaile, Philip N. Klein

ACM Trans. Algorithms, 2016

Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 16221).

Jeff Erickson, Philip N. Klein, Dániel Marx, Claire Mathieu

Dagstuhl Reports, 2016

The power of local search for clustering.

Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu

CoRR, 2016

Approximating connectivity domination in weighted bounded-genus graphs.

Vincent Cohen-Addad, Éric Colin de Verdière, Philip N. Klein, Claire Mathieu, David Meierfrankenfeld

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

2015

A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest.

Glencora Borradaile, Philip N. Klein, Claire Mathieu

ACM Trans. Algorithms, 2015

On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms.

Philip N. Klein, Neal E. Young

SIAM J. Comput., 2015

A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection.

Kyle Fox, Philip N. Klein, Shay Mozes

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

2014

Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs.

Erik D. Demaine, Mohammad Taghi Hajiaghayi, Philip N. Klein

ACM Trans. Algorithms, 2014

A subexponential parameterized algorithm for Subset TSP on planar graphs.

Philip N. Klein, Dániel Marx

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Approximating <i>k</i>-center in planar graphs.

David Eisenstat, Philip N. Klein, Claire Mathieu

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

A Cryptography Primer: Secrets and Promises

Philip N. Klein

Cambridge University Press, ISBN: 9781139084772, 2014

2013

Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 13421).

Glencora Borradaile, Philip N. Klein, Dániel Marx, Claire Mathieu

Dagstuhl Reports, 2013

Structured recursive separator decompositions for planar graphs in linear time.

Philip N. Klein, Shay Mozes, Christian Sommer

Proceedings of the Symposium on Theory of Computing Conference, 2013

Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs.

David Eisenstat, Philip N. Klein

Proceedings of the Symposium on Theory of Computing Conference, 2013

2012

An efficient polynomial-time approximation scheme for Steiner forest in planar graphs.

David Eisenstat, Philip N. Klein, Claire Mathieu

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

A polynomial-time approximation scheme for planar multiway cut.

MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Philip N. Klein, Claire Mathieu

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time.

Philip N. Klein, Dániel Marx

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011

Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter · n log n) Time.

Philip N. Klein, Shay Mozes

Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs.

Ken-ichi Kawarabayashi, Philip N. Klein, Christian Sommer

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010

Shortest paths in directed planar graphs with negative lengths: A linear-space <i>O</i>(<i>n</i> log² <i>n</i>)-time algorithm.

Philip N. Klein, Shay Mozes, Oren Weimann

ACM Trans. Algorithms, 2010

Multiple-source single-sink maximum flow in directed planar graphs in $O(n^{1.5} \log n)$ time

Philip N. Klein, Shay Mozes

CoRR, 2010

2009

An <i>O</i>(<i>n</i> log <i>n</i>) approximation scheme for Steiner tree in planar graphs.

Glencora Borradaile, Philip N. Klein, Claire Mathieu

ACM Trans. Algorithms, 2009

An <i>O</i>(<i>n</i> log <i>n</i>) algorithm for maximum <i>st</i>-flow in a directed planar graph.

Glencora Borradaile, Philip N. Klein

J. ACM, 2009

2008

A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights.

Philip N. Klein

SIAM J. Comput., 2008

The Two-Edge Connectivity Survivable Network Problem in Planar Graphs.

Glencora Borradaile, Philip N. Klein

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

2007

Steiner Tree in Planar Graphs: An <i>O</i> ( <i>n</i> log <i>n</i> ) Approximation Scheme with Singly-Exponential Dependence on Epsilon.

Glencora Borradaile, Philip N. Klein, Claire Mathieu

Proceedings of the Algorithms and Data Structures, 10th International Workshop, 2007

A polynomial-time approximation scheme for Steiner tree in planar graphs.

Glencora Borradaile, Claire Kenyon-Mathieu, Philip N. Klein

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2006

A subset spanner for Planar graphs, : with application to subset TSP.

Philip N. Klein

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

An <i>O (n log n)</i> algorithm for maximum <i>st</i>-flow in a directed planar graph.

Glencora Borradaile, Philip N. Klein

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

2005

Multiple-source shortest paths in planar graphs.

Philip N. Klein

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

A linear-time approximation scheme for planar weighted TSP.

Philip N. Klein

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004

Recognition of Shapes by Editing Their Shock Graphs.

Thomas B. Sebastian, Philip N. Klein, Benjamin B. Kimia

IEEE Trans. Pattern Anal. Mach. Intell., 2004

Approximation algorithms for finding low-degree subgraphs.

Philip N. Klein, Radha Krishnan, Balaji Raghavachari, R. Ravi

Networks, 2004

Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut.

David R. Karger, Philip N. Klein, Clifford Stein, Mikkel Thorup, Neal E. Young

Math. Oper. Res., 2004

2003

On Aligning Curves.

Thomas B. Sebastian, Philip N. Klein, Benjamin B. Kimia

IEEE Trans. Pattern Anal. Mach. Intell., 2003

Detecting Race Conditions in Parallel Programs that Use Semaphores.

Philip N. Klein, Robert H. B. Netzer, Hsueh-I Lu

Algorithmica, 2003

2002

Preprocessing an undirected planar network to enable fast approximate distance queries.

Philip N. Klein

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Shock-Based Indexing into Large Shape Databases.

Thomas B. Sebastian, Philip N. Klein, Benjamin B. Kimia

Proceedings of the Computer Vision, 2002

2001

Shape matching using edit-distance: an implementation.

Philip N. Klein, Thomas B. Sebastian, Benjamin B. Kimia

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Alignment-Based Recognition of Shape Outlines.

Thomas B. Sebastian, Philip N. Klein, Benjamin B. Kimia

Proceedings of the Visual Form 2001, 4th International Workshop on Visual Form, 2001

Recognition of Shapes by Editing Shock Graphs.

Thomas B. Sebastian, Philip N. Klein, Benjamin B. Kimia

Proceedings of the Eighth International Conference On Computer Vision (ICCV-01), Vancouver, British Columbia, Canada, July 7-14, 2001, 2001

2000

A tree-edit-distance algorithm for comparing simple, closed shapes.

Philip N. Klein, Srikanta Tirthapura, Daniel Sharvit, Benjamin B. Kimia

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Finding the closest lattice vector when it's unusually close.

Philip N. Klein

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Using router stamping to identify the source of IP packets.

Thomas W. Doeppner Jr., Philip N. Klein, Andrew Koyfman

Proceedings of the CCS 2000, 2000

1999

Approximation Algorithms.

Philip N. Klein, Neal E. Young

Proceedings of the Algorithms and Theory of Computation Handbook., 1999

1998

A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs.

Philip N. Klein, Sairam Subramanian

Algorithmica, 1998

A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP.

Sanjeev Arora, Michelangelo Grigni, David R. Karger, Philip N. Klein, Andrzej Woloszyn

Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

Space-Efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programs.

Philip N. Klein, Hsueh-I Lu

Proceedings of the Algorithms and Computation, 9th International Symposium, 1998

Computing the Edit-Distance between Unrooted Ordered Trees.

Philip N. Klein

Proceedings of the Algorithms, 1998

1997

Faster Shortest-Path Algorithms for Planar Graphs.

Monika Rauch Henzinger, Philip N. Klein, Satish Rao, Sairam Subramanian

J. Comput. Syst. Sci., 1997

A Randomized Parallel Algorithm for Single-Source Shortest Paths.

Philip N. Klein, Sairam Subramanian

J. Algorithms, 1997

Approximation Algorithms for Steiner and Directed Multicuts.

Philip N. Klein, Serge A. Plotkin, Satish Rao, Éva Tardos

J. Algorithms, 1997

1996

Efficient Parallel Algorithms for Chordal Graphs.

Philip N. Klein

SIAM J. Comput., 1996

Efficient Approximation Algorithms for Semidefinite Programs Arising from MAX CUT and COLORING.

Philip N. Klein, Hsueh-I Lu

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Finding Minimum Spanning Forests in Logarithmic Time and Linear Work Using Random Sampling.

Richard Cole, Philip N. Klein, Robert Endre Tarjan

Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures, 1996

Race-Condition Detection in Parallel Computation with Semaphores (Extended Abstract).

Philip N. Klein, Hsueh-I Lu, Robert H. B. Netzer

Proceedings of the Algorithms, 1996

1995

When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks.

Ajit Agrawal, Philip N. Klein, R. Ravi

SIAM J. Comput., 1995

A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees.

Philip N. Klein, R. Ravi

J. Algorithms, 1995

A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees.

David R. Karger, Philip N. Klein, Robert Endre Tarjan

J. ACM, 1995

An Approximate Max-Flow Min-Cut Relation for Unidirected Multicommodity Flow, with Applications.

Philip N. Klein, Satish Rao, Ajit Agrawal, R. Ravi

Comb., 1995

1994

Faster Approximation Algorithms for the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts.

Philip N. Klein, Serge A. Plotkin, Clifford Stein, Éva Tardos

SIAM J. Comput., 1994

A Data Structure for Bicategories, with Application to Speeding up an Approximation Algorithm.

Philip N. Klein

Inf. Process. Lett., 1994

A randomized linear-time algorithm for finding minimum spanning trees.

Philip N. Klein, Robert Endre Tarjan

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

1993

The Lattice Structure of Flow in Planar Graphs.

Samir Khuller, Joseph Naor, Philip N. Klein

SIAM J. Discret. Math., 1993

Towards Overcoming the Transitive-Closure Bottleneck: Efficient Parallel Algorithms for Planar Digraphs.

Ming-Yang Kao, Philip N. Klein

J. Comput. Syst. Sci., 1993

Parallelism, Preprocessing, and Reachability: A Hybrid Algorithm for Directed Graphs.

Philip N. Klein

J. Algorithms, 1993

A Parallel Algorithm for Approximating the Minimum Cycle Cover.

Philip N. Klein, Clifford Stein

Algorithmica, 1993

Detecting Race Conditions in Parallel Programs that Use One Semaphore.

Hsueh-I Lu, Philip N. Klein, Robert H. B. Netzer

Proceedings of the Algorithms and Data Structures, Third Workshop, 1993

A Fully Dynamic Approximation Scheme for All-Pairs Shortest Paths in Planar Graphs.

Philip N. Klein, Sairam Subramanian

Proceedings of the Algorithms and Data Structures, Third Workshop, 1993

Excluded minors, network decomposition, and multicommodity flow.

Philip N. Klein, Serge A. Plotkin, Satish Rao

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

On Gazit and Miller's Parallel Algorithm for Planar Separators: Achieving Greater Efficiency Through Random Sampling.

Philip N. Klein

Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, 1993

When cycles collapse: A general approximation technique for constrained two-connectivity problems.

Philip N. Klein, R. Ravi

Proceedings of the 3rd Integer Programming and Combinatorial Optimization Conference, Erice, Italy, April 29, 1993

A linear-processor polylog-time algorithm for shortest paths in planar graphs

Philip N. Klein, Sairam Subramanian

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992

A Parallel Randomized Approximation Scheme for Shortest Paths

Philip N. Klein, Sairam Sairam

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Approximation Through Local Optimality: Designing Networks with Small Degree.

R. Ravi, Balaji Raghavachari, Philip N. Klein

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1992

1991

Ordering Problems Approximated: Single-Processor Scheduling and Interval Graph Completion.

R. Ravi, Ajit Agrawal, Philip N. Klein

Proceedings of the Automata, Languages and Programming, 18th International Colloquium, 1991

Approximating Concurrent Flow with Unit Demands and Capacities: An Implementation.

James M. Borger, Sarah Kang, Philip N. Klein

Proceedings of the Network Flows And Matching, 1991

1990

A Parallel Algorithm for Eliminating Cycles in Undirected Graphs.

Philip N. Klein, Clifford Stein

Inf. Process. Lett., 1990

On the Time-Space Complexity of Reachability Queries for Preprocessed Graphs.

Lisa Hellerstein, Philip N. Klein, Robert Wilber

Inf. Process. Lett., 1990

Leighton-Rao Might Be Practical: Faster Approximation Algorithms for Concurrent Flow with Uniform Capacities

Philip N. Klein, Clifford Stein, Éva Tardos

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Approximation through Multicommodity Flow

Philip N. Klein, Ajit Agrawal, R. Ravi, Satish Rao

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1988

Parallel Time O(log n) Acceptance of Deterministic CFLs on an Exclusive-Write P-RAM.

Philip N. Klein, John H. Reif

SIAM J. Comput., 1988

An Efficient Parallel Algorithm for Planarity.

Philip N. Klein, John H. Reif

J. Comput. Syst. Sci., 1988