BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Glencora Borradaile

Glencora Borradaile appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsComputational GeometryDiscrete Mathematicsmath.COComputational Complexitycs.CYMachine Learningmath.AT

Catalog footprint

What is connected

24works
8topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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

Published work

24 published item(s)

preprint2020arXiv

Low-stretch spanning trees of graphs with bounded width

We study the problem of low-stretch spanning trees in graphs of bounded width: bandwidth, cutwidth, and treewidth. We show that any simple connected graph $G$ with a linear arrangement of bandwidth $b$ can be embedded into a distribution $\mathcal T$ of spanning trees such that the expected stretch of each edge of $G$ is $O(b^2)$. Our proof implies a linear time algorithm for sampling from $\mathcal T$. Therefore, we have a linear time algorithm that finds a spanning tree of $G$ with average stretch $O(b^2)$ with high probability. We also describe a deterministic linear-time algorithm for computing a spanning tree of $G$ with average stretch $O(b^3)$. For graphs of cutwidth $c$, we construct a spanning tree with stretch $O(c^2)$ in linear time. Finally, when $G$ has treewidth $k$ we provide a dynamic programming algorithm computing a minimum stretch spanning tree of $G$ that runs in polynomial time with respect to the number of vertices of $G$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Minimum bounded chains and minimum homologous chains in embedded simplicial complexes

We study two optimization problems on simplicial complexes with homology over $\mathbb{Z}_2$, the minimum bounded chain problem: given a $d$-dimensional complex $\mathcal{K}$ embedded in $\mathbb{R}^{d+1}$ and a null-homologous $(d-1)$-cycle $C$ in $\mathcal{K}$, find the minimum $d$-chain with boundary $C$, and the minimum homologous chain problem: given a $(d+1)$-manifold $\mathcal{M}$ and a $d$-chain $D$ in $\mathcal{M}$, find the minimum $d$-chain homologous to $D$. We show strong hardness results for both problems even for small values of $d$; $d = 2$ for the former problem, and $d=1$ for the latter problem. We show that both problems are APX-hard, and hard to approximate within any constant factor assuming the unique games conjecture. On the positive side, we show that both problems are fixed parameter tractable with respect to the size of the optimal solution. Moreover, we provide an $O(\sqrt{\log β_d})$-approximation algorithm for the minimum bounded chain problem where $β_d$ is the $d$th Betti number of $\mathcal{K}$. Finally, we provide an $O(\sqrt{\log n_{d+1}})$-approximation algorithm for the minimum homologous chain problem where $n_{d+1}$ is the number of $d$-simplices in $\mathcal{M}$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Whose Tweets are Surveilled for the Police: An Audit of Social-Media Monitoring Tool via Log Files

Social media monitoring by law enforcement is becoming commonplace, but little is known about what software packages for it do. Through public records requests, we obtained log files from the Corvallis (Oregon) Police Department's use of social media monitoring software called DigitalStakeout. These log files include the results of proprietary searches by DigitalStakeout that were running over a period of 13 months and include 7240 social media posts. In this paper, we focus on the Tweets logged in this data and consider the racial and ethnic identity (through manual coding) of the users that are therein flagged by DigitalStakeout. We observe differences in the demographics of the users whose Tweets are flagged by DigitalStakeout compared to the demographics of the Twitter users in the region, however, our sample size is too small to determine significance. Further, the demographics of the Twitter users in the region do not seem to reflect that of the residents of the region, with an apparent higher representation of Black and Hispanic people. We also reconstruct the keywords related to a Narcotics report set up by DigitalStakeout for the Corvallis Police Department and find that these keywords flag Tweets unrelated to narcotics or flag Tweets related to marijuana, a drug that is legal for recreational use in Oregon. Almost all of the keywords have a common meaning unrelated to narcotics (e.g.\ broken, snow, hop, high) that call into question the utility that such a keyword based search could have to law enforcement.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A PTAS for Three-Edge Connectivity in Planar Graphs

We consider the problem of finding the minimum-weight subgraph that satisfies given connectivity requirements. Specifically, given a requirement $r \in \{0,1,2,3\}$ for every vertex, we seek the minimum-weight subgraph that contains, for every pair of vertices $u$ and $v$, at least $\min\{ r(v), r(u)\}$ edge-disjoint $u$-to-$v$ paths. We give a polynomial-time approximation scheme (PTAS) for this problem when the input graph is planar and the subgraph may use multiple copies of any given edge. This generalizes an earlier result for $r \in \{0,1,2\}$. In order to achieve this PTAS, we prove some properties of triconnected planar graphs that may be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Minimum cycle and homology bases of surface embedded graphs

We study the problems of finding a minimum cycle basis (a minimum weight set of cycles that form a basis for the cycle space) and a minimum homology basis (a minimum weight set of cycles that generates the $1$-dimensional ($\mathbb{Z}_2$)-homology classes) of an undirected graph embedded on a surface. The problems are closely related, because the minimum cycle basis of a graph contains its minimum homology basis, and the minimum homology basis of the $1$-skeleton of any graph is exactly its minimum cycle basis. For the minimum cycle basis problem, we give a deterministic $O(n^ω+2^{2g}n^2+m)$-time algorithm for graphs embedded on an orientable surface of genus $g$. The best known existing algorithms for surface embedded graphs are those for general graphs: an $O(m^ω)$ time Monte Carlo algorithm and a deterministic $O(nm^2/\log n + n^2 m)$ time algorithm. For the minimum homology basis problem, we give a deterministic $O((g+b)^3 n \log n + m)$-time algorithm for graphs embedded on an orientable or non-orientable surface of genus $g$ with $b$ boundary components, assuming shortest paths are unique, improving on existing algorithms for many values of $g$ and $n$. The assumption of unique shortest paths can be avoided with high probability using randomization or deterministically by increasing the running time of the homology basis algorithm by a factor of $O(\log n)$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Optimal dynamic program for r-domination problems over tree decompositions

There has been recent progress in showing that the exponential dependence on treewidth in dynamic programming algorithms for solving NP-hard problems are optimal under the Strong Exponential Time Hypothesis (SETH). We extend this work to $r$-domination problems. In $r$-dominating set, one wished to find a minimum subset $S$ of vertices such that every vertex of $G$ is within $r$ hops of some vertex in $S$. In connected $r$-dominating set, one additionally requires that the set induces a connected subgraph of $G$. We give a $O((2r+1)^{\mathrm{tw}} n)$ time algorithm for $r$-dominating set and a $O((2r+2)^{\mathrm{tw}} n^{O(1)})$ time algorithm for connected $r$-dominating set in $n$-vertex graphs of treewidth $\mathrm{tw}$. We show that the running time dependence on $r$ and $\mathrm{tw}$ is the best possible under SETH. This adds to earlier observations that a "+1" in the denominator is required for connectivity constraints.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Planar Induced Subgraphs of Sparse Graphs

We show that every graph has an induced pseudoforest of at least $n-m/4.5$ vertices, an induced partial 2-tree of at least $n-m/5$ vertices, and an induced planar subgraph of at least $n-m/5.2174$ vertices. These results are constructive, implying linear-time algorithms to find the respective induced subgraphs. We also show that the size of the largest $K_h$-minor-free graph in a given graph can sometimes be at most $n-m/6+o(m)$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The two-edge connectivity survivable-network design problem in planar graphs

Consider the following problem: given a graph with edge costs and a subset Q of vertices, find a minimum-cost subgraph in which there are two edge-disjoint paths connecting every pair of vertices in Q. The problem is a failure-resilient analog of the Steiner tree problem arising, for example, in telecommunications applications. We study a more general mixed-connectivity formulation, also employed in telecommunications optimization. Given a number (or requirement) r(v) in {0, 1, 2} for each vertex v in the graph, find a minimum-cost subgraph in which there are min{r(u), r(v)} edge-disjoint u-to-v paths for every pair u, v of vertices. We address the problem in planar graphs, considering a popular relaxation in which the solution is allowed to use multiple copies of the input-graph edges (paying separately for each copy). The problem is max SNP-hard in general graphs and strongly NP-hard in planar graphs. We give the first polynomial-time approximation scheme in planar graphs. The running time is O(n log n). Under the additional restriction that the requirements are only non-zero for vertices on the boundary of a single face of a planar graph, we give a polynomial-time algorithm to find the optimal solution.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Towards single face shortest vertex-disjoint paths in undirected planar graphs

Given $k$ pairs of terminals $\{(s_{1}, t_{1}), \ldots, (s_{k}, t_{k})\}$ in a graph $G$, the min-sum $k$ vertex-disjoint paths problem is to find a collection $\{Q_{1}, Q_{2}, \ldots, Q_{k}\}$ of vertex-disjoint paths with minimum total length, where $Q_{i}$ is an $s_i$-to-$t_i$ path between $s_i$ and $t_i$. We consider the problem in planar graphs, where little is known about computational tractability, even in restricted cases. Kobayashi and Sommer propose a polynomial-time algorithm for $k \le 3$ in undirected planar graphs assuming all terminals are adjacent to at most two faces. Colin de Verdiere and Schrijver give a polynomial-time algorithm when all the sources are on the boundary of one face and all the sinks are on the boundary of another face and ask about the existence of a polynomial-time algorithm provided all terminals are on a common face. We make progress toward Colin de Verdiere and Schrijver's open question by giving an $O(kn^5)$ time algorithm for undirected planar graphs when $\{(s_{1}, t_{1}), \ldots, (s_{k}, t_{k})\}$ are in counter-clockwise order on a common face.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Covering nearly surface-embedded graphs with a fixed number of balls

A recent result of Chepoi, Estellon and Vaxes [DCG '07] states that any planar graph of diameter at most 2R can be covered by a constant number of balls of size R; put another way, there are a constant-sized subset of vertices within which every other vertex is distance half the diameter. We generalize this result to graphs embedded on surfaces of fixed genus with a fixed number of apices, making progress toward the conjecture that graphs excluding a fixed minor can also be covered by a constant number of balls. To do so, we develop two tools which may be of independent interest. The first gives a bound on the density of graphs drawn on a surface of genus $g$ having a limit on the number of pairwise-crossing edges. The second bounds the size of a non-contractible cycle in terms of the Euclidean norm of the degree sequence of a graph embedded on surface.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Improving Robustness of Next-Hop Routing

A weakness of next-hop routing is that following a link or router failure there may be no routes between some source-destination pairs, or packets may get stuck in a routing loop as the protocol operates to establish new routes. In this article, we address these weaknesses by describing mechanisms to choose alternate next hops. Our first contribution is to model the scenario as the following {\sc tree augmentation} problem. Consider a mixed graph where some edges are directed and some undirected. The directed edges form a spanning tree pointing towards the common destination node. Each directed edge represents the unique next hop in the routing protocol. Our goal is to direct the undirected edges so that the resulting graph remains acyclic and the number of nodes with outdegree two or more is maximized. These nodes represent those with alternative next hops in their routing paths. We show that {\sc tree augmentation} is NP-hard in general and present a simple $\frac{1}{2}$-approximation algorithm. We also study 3 special cases. We give exact polynomial-time algorithms for when the input spanning tree consists of exactly 2 directed paths or when the input graph has bounded treewidth. For planar graphs, we present a polynomial-time approximation scheme when the input tree is a breadth-first search tree. To the best of our knowledge, {\sc tree augmentation} has not been previously studied.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Boundary-to-boundary flows in planar graphs

We give an iterative algorithm for finding the maximum flow between a set of sources and sinks that lie on the boundary of a planar graph. Our algorithm uses only O(n) queries to simple data structures, achieving an O(n log n) running time that we expect to be practical given the use of simple primitives. The only existing algorithm for this problem uses divide and conquer and, in order to achieve an O(n log n) running time, requires the use of the (complicated) linear-time shortest-paths algorithm for planar graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Maximum st-flow in directed planar graphs via shortest paths

Minimum cuts have been closely related to shortest paths in planar graphs via planar duality - so long as the graphs are undirected. Even maximum flows are closely related to shortest paths for the same reason - so long as the source and the sink are on a common face. In this paper, we give a correspondence between maximum flows and shortest paths via duality in directed planar graphs with no constraints on the source and sink. We believe this a promising avenue for developing algorithms that are more practical than the current asymptotically best algorithms for maximum st-flow.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time

For an undirected $n$-vertex planar graph $G$ with non-negative edge-weights, we consider the following type of query: given two vertices $s$ and $t$ in $G$, what is the weight of a min $st$-cut in $G$? We show how to answer such queries in constant time with $O(n\log^4n)$ preprocessing time and $O(n\log n)$ space. We use a Gomory-Hu tree to represent all the pairwise min cuts implicitly. Previously, no subquadratic time algorithm was known for this problem. Since all-pairs min cut and the minimum cycle basis are dual problems in planar graphs, we also obtain an implicit representation of a minimum cycle basis in $O(n\log^4n)$ time and $O(n\log n)$ space. Additionally, an explicit representation can be obtained in $O(C)$ time and space where $C$ is the size of the basis. These results require that shortest paths are unique. This can be guaranteed either by using randomization without overhead, or deterministically with an additional $\log^2 n$ factor in the preprocessing times.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Near-Linear-Time Deterministic Plane Steiner Spanners and TSP Approximation for Well-Spaced Point Sets

We describe an algorithm that takes as input n points in the plane and a parameter ε, and produces as output an embedded planar graph having the given points as a subset of its vertices in which the graph distances are a (1 + ε)-approximation to the geometric distances between the given points. For point sets in which the Delaunay triangulation has bounded sharpest angle, our algorithm's output has O(n) vertices, its weight is O(1) times the minimum spanning tree weight, and the algorithm's running time is bounded by O(n \sqrt{log log n}). We use this result in a similarly fast deterministic approximation scheme for the traveling salesperson problem.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Batch Active Learning via Coordinated Matching

Most prior work on active learning of classifiers has focused on sequentially selecting one unlabeled example at a time to be labeled in order to reduce the overall labeling effort. In many scenarios, however, it is desirable to label an entire batch of examples at once, for example, when labels can be acquired in parallel. This motivates us to study batch active learning, which iteratively selects batches of $k>1$ examples to be labeled. We propose a novel batch active learning method that leverages the availability of high-quality and efficient sequential active-learning policies by attempting to approximate their behavior when applied for $k$ steps. Specifically, our algorithm first uses Monte-Carlo simulation to estimate the distribution of unlabeled examples selected by a sequential policy over $k$ step executions. The algorithm then attempts to select a set of $k$ examples that best matches this distribution, leading to a combinatorial optimization problem that we term "bounded coordinated matching". While we show this problem is NP-hard in general, we give an efficient greedy solution, which inherits approximation bounds from supermodular minimization theory. Our experimental results on eight benchmark datasets show that the proposed approach is highly effective

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Connectivity Oracles for Planar Graphs

We consider dynamic subgraph connectivity problems for planar graphs. In this model there is a fixed underlying planar graph, where each edge and vertex is either "off" (failed) or "on" (recovered). We wish to answer connectivity queries with respect to the "on" subgraph. The model has two natural variants, one in which there are $d$ edge/vertex failures that precede all connectivity queries, and one in which failures/recoveries and queries are intermixed. We present a $d$-failure connectivity oracle for planar graphs that processes any $d$ edge/vertex failures in $sort(d,n)$ time so that connectivity queries can be answered in $pred(d,n)$ time. (Here $sort$ and $pred$ are the time for integer sorting and integer predecessor search over a subset of $[n]$ of size $d$.) Our algorithm has two discrete parts. The first is an algorithm tailored to triconnected planar graphs. It makes use of Barnette's theorem, which states that every triconnected planar graph contains a degree-3 spanning tree. The second part is a generic reduction from general (planar) graphs to triconnected (planar) graphs. Our algorithm is, moreover, provably optimal. An implication of Patrascu and Thorup's lower bound on predecessor search is that no $d$-failure connectivity oracle (even on trees) can beat $pred(d,n)$ query time. We extend our algorithms to the subgraph connectivity model where edge/vertex failures (but no recoveries) are intermixed with connectivity queries. In triconnected planar graphs each failure and query is handled in $O(\log n)$ time (amortized), whereas in general planar graphs both bounds become $O(\log^2 n)$.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs

We present the first polynomial-time approximation schemes (PTASes) for the following subset-connectivity problems in edge-weighted graphs of bounded genus: Steiner tree, low-connectivity survivable-network design, and subset TSP. The schemes run in O(n log n) time for graphs embedded on both orientable and non-orientable surfaces. This work generalizes the PTAS frameworks of Borradaile, Klein, and Mathieu from planar graphs to bounded-genus graphs: any future problems shown to admit the required structure theorem for planar graphs will similarly extend to bounded-genus graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The Knapsack Problem with Neighbour Constraints

We study a constrained version of the knapsack problem in which dependencies between items are given by the adjacencies of a graph. In the 1-neighbour knapsack problem, an item can be selected only if at least one of its neighbours is also selected. In the all-neighbours knapsack problem, an item can be selected only if all its neighbours are also selected. We give approximation algorithms and hardness results when the nodes have both uniform and arbitrary weight and profit functions, and when the dependency graph is directed and undirected.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Randomly removing g handles at once

Indyk and Sidiropoulos (2007) proved that any orientable graph of genus $g$ can be probabilistically embedded into a graph of genus $g-1$ with constant distortion. Viewing a graph of genus $g$ as embedded on the surface of a sphere with $g$ handles attached, Indyk and Sidiropoulos' method gives an embedding into a distribution over planar graphs with distortion $2^{O(g)}$, by iteratively removing the handles. By removing all $g$ handles at once, we present a probabilistic embedding with distortion $O(g^2)$ for both orientable and non-orientable graphs. Our result is obtained by showing that the nimum-cut graph of Erickson and Har Peled (2004) has low dilation, and then randomly cutting this graph out of the surface using the Peeling Lemma of Lee and Sidiropoulos (2009).

0 citations0 reviewsNo code linkedOpen access