Philip N. Klein

Generating author description...

All published works

Action	Title	Year	Authors
+	A quasipolynomial (2 + <i>ε</i> )-approximation for planar sparsest cut	2021	Vincent Cohen-Addad Anupam Gupta Philip N. Klein Jason Li
+	A Quasipolynomial $(2+\varepsilon)$-Approximation for Planar Sparsest Cut	2021	Vincent Cohen-Addad Anupam Gupta Philip N. Klein Jason Li
+ PDF Chat	On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs	2020	Vincent Cohen-Addad Arnold Filtser Philip N. Klein Hung Le
+	On the Computational Tractability of a Geographic Clustering Problem Arising in Redistricting	2020	Vincent Cohen-Addad Philip N. Klein Dániel Marx
+ PDF Chat	New hardness results for planar graph problems in p and an algorithm for sparsest cut	2020	Amir Abboud Vincent Cohen-Addad Philip N. Klein
+	On the computational tractability of a geographic clustering problem arising in redistricting	2020	Vincent Cohen-Addad Philip N. Klein Dániel Marx
+	On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs	2020	Vincent Cohen-Addad Arnold Filtser Philip N. Klein Hung Le
+	New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut	2020	Amir Abboud Vincent Cohen-Addad Philip N. Klein
+	A PTAS for Bounded-Capacity Vehicle Routing in Planar Graphs	2019	Amariah Becker Philip N. Klein Aaron Schild
+ PDF Chat	Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics	2019	Vincent Cohen-Addad Philip N. Klein Claire Mathieu
+ PDF Chat	A PTAS for Bounded-Capacity Vehicle Routing in Planar Graphs	2019	Amariah Becker Philip N. Klein Aaron Schild
+	A near-linear time minimum Steiner cut algorithm for planar graphs	2019	Stephen Jue Philip N. Klein
+	A PTAS for Bounded-Capacity Vehicle Routing in Planar Graphs	2019	Amariah Becker Philip N. Klein Aaron Schild
+ PDF Chat	Balanced centroidal power diagrams for redistricting	2018	Vincent Cohen-Addad Philip N. Klein Neal E. Young
+	Balanced power diagrams for redistricting.	2017	Vincent Cohen-Addad Philip N. Klein Neal E. Young
+	Polynomial-Time Approximation Schemes for k-Center and Bounded-Capacity Vehicle Routing in Metrics with Bounded Highway Dimension.	2017	Amariah Becker Philip N. Klein David Saulpic
+	Polynomial-Time Approximation Schemes for Bounded-Capacity Vehicle Routing and Clustering Problems in Metrics with Bounded Highway Dimension	2017	Amariah Becker Philip N. Klein David Saulpic
+ PDF Chat	Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time	2017	Glencora Borradaile Philip N. Klein Shay Mozes Yahav Nussbaum Christian Wulff‐Nilsen
+	Balanced power diagrams for redistricting	2017	Vincent Cohen-Addad Philip N. Klein Neal E. Young
+	Polynomial-Time Approximation Schemes for k-Center and Bounded-Capacity Vehicle Routing in Graphs with Bounded Highway Dimension	2017	Amariah Becker Philip N. Klein David Saulpic
+ PDF Chat	Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics	2016	Vincent Cohen-Addad Philip N. Klein Claire Mathieu
+ PDF Chat	The Two-Edge Connectivity Survivable-Network Design Problem in Planar Graphs	2016	Glencora Borradaile Philip N. Klein
+	The power of local search for clustering.	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	2016	Vincent Cohen-Addad Philip N. Klein Claire Mathieu
+ PDF Chat	A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection	2015	Kyle Fox Philip N. Klein Shay Mozes
+	A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection	2015	Kyle Fox Philip N. Klein Shay Mozes
+ PDF Chat	A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest	2015	Glencora Borradaile Philip N. Klein Claire Mathieu
+ PDF Chat	On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms	2015	Philip N. Klein Neal E. Young
+	A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection	2015	Kyle Fox Philip N. Klein Shay Mozes
+	Number Theory	2014	Philip N. Klein
+	Coding the Matrix: Linear Algebra through Applications to Computer Science	2013	Philip N. Klein
+ PDF Chat	Structured recursive separator decompositions for planar graphs in linear time	2013	Philip N. Klein Shay Mozes Christian Sommer
+ PDF Chat	An efficient polynomial-time approximation scheme for Steiner forest in planar graphs	2012	David Eisenstat Philip N. Klein Claire Mathieu
+	Structured Recursive Separator Decompositions for Planar Graphs in Linear Time	2012	Philip N. Klein Shay Mozes Christian Sommer
+ PDF Chat	Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time	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	2011	Glencora Borradaile Philip N. Klein Shay Mozes Yahav Nussbaum Christian Wulff‐Nilsen
+	Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameternlog(n)) Time	2011	Philip N. Klein Shay Mozes
+ PDF Chat	Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter · n log n) Time	2011	Philip N. Klein Shay Mozes
+ PDF Chat	Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs	2011	Ken‐ichi Kawarabayashi Philip N. Klein Christian Sommer
+	Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time	2011	Glencora Borradaile Philip N. Klein Shay Mozes Yahav Nussbaum Christian Wulff-Nilsen
+	Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameternlog(n)) Time	2011	Philip N. Klein Shay Mozes
+	Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in $O(n^{1.5} \log n)$ Time	2010	Philip N. Klein Shay Mozes
+	Multiple-source single-sink maximum flow in directed planar graphs in $O(n^{1.5} \log n)$ time	2010	Philip N. Klein Shay Mozes
+ PDF Chat	A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest	2008	Glencora Borradaile Philip N. Klein Claire Mathieu
+ PDF Chat	Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut	2004	David R. Karger Philip N. Klein Clifford Stein Mikkel Thorup Neal E. Young
+ PDF Chat	Constructing 2D curve atlases	2002	Thomas Sebastian Joseph J. Crisco Philip N. Klein Benjamin B. Kimia
+	Rounding algorithms for a geometric embedding of minimum multiway cut	1999	David R. Karger Philip N. Klein Clifford Stein Mikkel Thorup Neal E. Young
+ PDF Chat	Space-Efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programs	1998	Philip N. Klein Hsueh-I Lu
+	Efficient approximation algorithms for semidefinite programs arising from MAX CUT and COLORING	1996	Philip N. Klein Hsueh-I Lu
+	Ordering problems approximated: single-processor scheduling and interval graph completion	1991	R. Ravi Ajit Agrawal Philip N. Klein
+	A parallel algorithm for eliminating cycles in undirected graphs	1990	Philip N. Klein Clifford Stein

Common Coauthors

Coauthor	Papers Together
Vincent Cohen-Addad	15
Shay Mozes	14
Glencora Borradaile	7
Claire Mathieu	7
Amariah Becker	6
Neal E. Young	6
Yahav Nussbaum	4
Kyle Fox	3
Christian Wulff‐Nilsen	3
David Saulpic	3
Aaron Schild	3
Clifford Stein	3
Amir Abboud	2
Dániel Marx	2
David R. Karger	2
Mikkel Thorup	2
Arnold Filtser	2
Hung Le	2
Christian Sommer	2
Anupam Gupta	2
Jason Li	2
Hsueh-I Lu	2
Thomas Sebastian	1
David Eisenstat	1
Joseph J. Crisco	1
Ajit Agrawal	1
Benjamin B. Kimia	1
R. Ravi	1
Christian Wulff-Nilsen	1
Christian Sommer	1
Stephen Jue	1
Ken‐ichi Kawarabayashi	1

Commonly Cited References

Action	Title	Year	Authors	# of times referenced
+	A unified framework for approximating and clustering data	2011	Dan Feldman Michael Langberg	4
+ PDF Chat	A Quasipolynomial Time Approximation Scheme for Euclidean Capacitated Vehicle Routing	2014	Aparna Das Claire Mathieu	4
+ PDF Chat	Maximum Flow in Directed Planar Graphs with Vertex Capacities	2010	Haim Kaplan Yahav Nussbaum	4
+ PDF Chat	Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs	2011	Ken‐ichi Kawarabayashi Philip N. Klein Christian Sommer	4
+ PDF Chat	Shortest Paths in Planar Graphs with Real Lengths in O(nlog2 n/loglogn) Time	2010	Shay Mozes Christian Wulff‐Nilsen	4
+	Embeddings of Topological Graphs: Lossy Invariants, Linearization, and 2-Sums	2008	Amit Chakrabarti Alexander Jaffe James R. Lee Justin Vincent	4
+ PDF Chat	Maintaining information in fully dynamic trees with top trees	2005	Stephen Alstrup Jacob Holm Kristian de Lichtenberg Mikkel Thorup	4
+ PDF Chat	Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs	2012	Glencora Borradaile Erik D. Demaine Siamak Tazari	3
+ PDF Chat	Approximating k-median via pseudo-approximation	2013	Shi Li Ola Svensson	3
+ PDF Chat	Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming	1995	Michel X. Goemans David P. Williamson	3
+	A survey of very large-scale neighborhood search techniques	2002	Ravindra K. Ahuja Özlem Ergün James B. Orlin Abraham P. Punnen	3
+	Small distortion and volume preserving embeddings for planar and Euclidean metrics	1999	Satish Rao	3
+	Shortest non-trivial cycles in directed and undirected surface graphs	2013	Kyle Fox	2
+ PDF Chat	Minor-Free Graphs Have Light Spanners	2017	Glencora Borradaile Hung Le Christian Wulff‐Nilsen	2
+	Redistricting: Drawing the Line	2017	Sachet Bangia Christy V. Graves Gregory Herschlag Han Sung Kang Justin Luo Jonathan C. Mattingly Robert Ravier	2
+ PDF Chat	Approximating $k$-Median via Pseudo-Approximation	2016	Shi Li Ola Svensson	2
+	Metric embedding via shortest path decompositions	2018	Ittai Abraham Arnold Filtser Anupam Gupta Ofer Neiman	2
+ PDF Chat	A PTAS for Bounded-Capacity Vehicle Routing in Planar Graphs	2019	Amariah Becker Philip N. Klein Aaron Schild	2
+	Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization	1995	Farid Alizadeh	2
+ PDF Chat	An Interior-Point Method for Semidefinite Programming	1996	Christoph Helmberg Franz Rendl Robert J. Vanderbei Henry Wolkowicz	2
+ PDF Chat	Bounded geometries, fractals, and low-distortion embeddings	2004	Anupam Gupta Robert Krauthgamer J.R. Lee	2
+ PDF Chat	Approximate graph coloring by semidefinite programming	2002	David R. Karger R. Motwani Madhu Sudan	2
+ PDF Chat	Clustering under Perturbation Resilience	2016	Maria Florina Balcan Yingyu Liang	2
+ PDF Chat	Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs	2015	Andreas Emil Feldmann	2
+ PDF Chat	The Greedy Spanner is Existentially Optimal	2016	Arnold Filtser Shay Solomon	2
+ PDF Chat	PTAS FOR k-TOUR COVER PROBLEM ON THE PLANE FOR MODERATELY LARGE VALUES OF k	2010	Anna Adamaszek Artur Czumaj Andrzej Lingas	2
+ PDF Chat	Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring	2005	Erik D. Demaine Mohammad Taghi Hajiaghayi Ken‐ichi Kawarabayashi	2
+	Shortest non-trivial cycles in directed surface graphs	2011	Jeff Erickson	2
+ PDF Chat	Expander flows, geometric embeddings and graph partitioning	2009	Sanjeev Arora Satish Rao Umesh Vazirani	2
+	A Separator Theorem in Minor-Closed Classes	2010	Ken‐ichi Kawarabayashi Bruce Reed	2
+	On the Shannon capacity of a graph	1979	László Lovász	2
+ PDF Chat	Parallel approximation algorithms for facility-location problems	2010	Guy E. Blelloch Kanat Tangwongsan	2
+ PDF Chat	Local Tree-Width, Excluded Minors, and Approximation Algorithms	2003	Martin Grohe	2
+	Finding the Maximal Empty Rectangle Containing a Query Point	2011	Haim Kaplan Micha Sharir	2
+ PDF Chat	Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time	2010	David Eppstein Maarten Löffler Darren Strash	2
+ PDF Chat	Separators for sphere-packings and nearest neighbor graphs	1997	Gary L. Miller Shang‐Hua Teng William P. Thurston Stephen A. Vavasis	2
+ PDF Chat	PTAS for k-Tour Cover Problem on the Plane for Moderately Large Values of k	2009	Anna Adamaszek Artur Czumaj Andrzej Lingas	2
+ PDF Chat	A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection	2015	Kyle Fox Philip N. Klein Shay Mozes	2
+	Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images	1984	Stuart Geman Donald Geman	2
+ PDF Chat	Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter · n log n) Time	2011	Philip N. Klein Shay Mozes	2
+	The Hardness of Approximation of Euclidean k-means	2015	Pranjal Awasthi Moses Charikar Ravishankar Krishnaswamy Ali Kemal Sinop	2
+	An Interior-Point Method for Minimizing the Maximum Eigenvalue of a Linear Combination of Matrices	1993	Florian Jarre	2
+	An Improved Decomposition Theorem for Graphs Excluding a Fixed Minor	2003	Jittat Fakcharoenphol Kunal Talwar	2
+	Spectral partitioning works: planar graphs and finite element meshes	1996	Daniel A. Spielman Shang‐Hua Teng	2
+	Interior Point Methods for the Monotone Linear Complementarity Problem in Symmetric Matrices	1995	Masakazu Kojima Susumu Shindoh Shinji Hara	2
+ PDF Chat	Centroidal Voronoi Tessellations: Applications and Algorithms	1999	Qiang Du Vance Faber Max Gunzburger	2
+	Separating a Voronoi Diagram.	2014	Vijay Bhattiprolu Sariel Har-Peled	2
+	On Variants of k-means Clustering	2015	Sayan Bandyapadhyay Kasturi Varadarajan	2
+ PDF Chat	Preserving Terminal Distances Using Minors	2014	Robert Krauthgamer Huy L. Nguyễn Tamar Zondiner	2
+ PDF Chat	Are Stable Instances Easy?	2012	Yonatan Bilu Nathan Linial	2