BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Philip N. Klein

Philip N. Klein contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and Algorithms

Trust snapshot

Quick read

Trust 17 - UnverifiedVerification L1Unclaimed author
4works
0followers
1topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

4 published item(s)

preprint2020arXiv

New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut

The Sparsest Cut is a fundamental optimization problem that has been extensively studied. For planar inputs the problem is in $P$ and can be solved in $\tilde{O}(n^3)$ time if all vertex weights are $1$. Despite a significant amount of effort, the best algorithms date back to the early 90's and can only achieve $O(\log n)$-approximation in $\tilde{O}(n)$ time or a constant factor approximation in $\tilde{O}(n^2)$ time [Rao, STOC92]. Our main result is an $Ω(n^{2-ε})$ lower bound for Sparsest Cut even in planar graphs with unit vertex weights, under the $(min,+)$-Convolution conjecture, showing that approximations are inevitable in the near-linear time regime. To complement the lower bound, we provide a constant factor approximation in near-linear time, improving upon the 25-year old result of Rao in both time and accuracy. Our lower bound accomplishes a repeatedly raised challenge by being the first fine-grained lower bound for a natural planar graph problem in P. Moreover, we prove near-quadratic lower bounds under SETH for variants of the closest pair problem in planar graphs, and use them to show that the popular Average-Linkage procedure for Hierarchical Clustering cannot be simulated in truly subquadratic time. We prove an $Ω(n/\log{n})$ lower bound on the number of communication rounds required to compute the weighted diameter of a network in the CONGEST model, even when the underlying graph is planar and all nodes are $D=4$ hops away from each other. This is the first poly($n$) + $ω(D)$ lower bound in the planar-distributed setting, and it complements the recent poly$(D, \log{n})$ upper bounds of Li and Parter [STOC 2019] for (exact) unweighted diameter and for ($1+ε$) approximate weighted diameter.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

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

Understanding the structure of minor-free metrics, namely shortest path metrics obtained over a weighted graph excluding a fixed minor, has been an important research direction since the fundamental work of Robertson and Seymour. A fundamental idea that helps both to understand the structural properties of these metrics and lead to strong algorithmic results is to construct a "small-complexity" graph that approximately preserves distances between pairs of points of the metric. We show the two following structural results for minor-free metrics: 1. Construction of a light subset spanner. Given a subset of vertices called terminals, and $ε$, in polynomial time we construct a subgraph that preserves all pairwise distances between terminals up to a multiplicative $1+ε$ factor, of total weight at most $O_ε(1)$ times the weight of the minimal Steiner tree spanning the terminals. 2. Construction of a stochastic metric embedding into low treewidth graphs with expected additive distortion $εD$. Namely, given a minor free graph $G=(V,E,w)$ of diameter $D$, and parameter $ε$, we construct a distribution $\mathcal{D}$ over dominating metric embeddings into treewidth-$O_ε(\log n)$ graphs such that the additive distortion is at most $εD$. One of our important technical contributions is a novel framework that allows us to reduce \emph{both problems} to problems on simpler graphs of bounded diameter. Our results have the following algorithmic consequences: (1) the first efficient approximation scheme for subset TSP in minor-free metrics; (2) the first approximation scheme for vehicle routing with bounded capacity in minor-free metrics; (3) the first efficient approximation scheme for vehicle routing with bounded capacity on bounded genus metrics.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

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

Redistricting is the problem of dividing a state into a number $k$ of regions, called districts. Voters in each district elect a representative. The primary criteria are: each district is connected, district populations are equal (or nearly equal), and districts are "compact". There are multiple competing definitions of compactness, usually minimizing some quantity. One measure that has been recently promoted by Duchin and others is number of cut edges. In redistricting, one is given atomic regions out of which each district must be built. The populations of the atomic regions are given. Consider the graph with one vertex per atomic region (with weight equal to the region's population) and an edge between atomic regions that share a boundary. A districting plan is a partition of vertices into $k$ parts, each connnected, of nearly equal weight. The districts are considered compact to the extent that the plan minimizes the number of edges crossing between different parts. Consider two problems: find the most compact districting plan, and sample districting plans under a compactness constraint uniformly at random. Both problems are NP-hard so we restrict the input graph to have branchwidth at most $w$. (A planar graph's branchwidth is bounded by its diameter.) If both $k$ and $w$ are bounded by constants, the problems are solvable in polynomial time. Assume vertices have weight~1. One would like algorithms whose running times are of the form $O(f(k,w) n^c)$ for some constant $c$ independent of $k$ and $w$, in which case the problems are said to be fixed-parameter tractable with respect to $k$ and $w$). We show that, under a complexity-theoretic assumption, no such algorithms exist. However, we do give algorithms with running time $O(c^wn^{k+1})$. Thus if the diameter of the graph is moderately small and the number of districts is very small, our algorithm is useable.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

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

We consider the Minimum Steiner Cut problem on undirected planar graphs with non-negative edge weights. This problem involves finding the minimum cut of the graph that separates a specified subset $X$ of vertices (terminals) into two parts. This problem is of theoretical interest because it generalizes two classical optimization problems, Minimum $s$-$t$ Cut and Minimum Cut, and of practical importance because of its application to computing a lower bound for Steiner (Subset) TSP. Our algorithm has running time $O(n\log{n}\log{k})$ where $k$ is the number of terminals.

0 citations0 reviewsNo code linkedOpen access