11 papers
Sampling Arborescences in Parallel
Nima Anari, Nathan Hu, Amin Saberi +1
We study the problem of sampling a uniformly random directed rooted spanning tree, also known as an arborescence, from a possibly weighted directed graph. Classically, this problem…
Algorithms and Hardness for Linear Algebra on Geometric Graphs
Josh Alman, Timothy Chu, Aaron Schild +1
For a function , and a set of points, the $\mathsf{K…
Improved Distributed Approximations for Maximum Independent Set
Ken-ichi Kawarabayashi, Seri Khoury, Aaron Schild +1
We present improved results for approximating maximum-weight independent set ($\MaxIS$) in the CONGEST and LOCAL models of distributed computing. Given an input graph, let and…
Network design for s-t effective resistance
Pak Hay Chan, Lap Chi Lau, Aaron Schild +2
We consider a new problem of designing a network with small - effective resistance. In this problem, we are given an undirected graph , two designated vertices $s,t…
A PTAS for Bounded-Capacity Vehicle Routing in Planar Graphs
Amariah Becker, Philip N. Klein, Aaron Schild
The Capacitated Vehicle Routing problem is to find a minimum-cost set of tours that collectively cover clients in a graph, such that each tour starts and ends at a specified depot…
Semi-Online Bipartite Matching
Ravi Kumar, Manish Purohit, Aaron Schild +2
In this paper we introduce the \emph{semi-online} model that generalizes the classical online computational model. The semi-online model postulates that the unknown future has a pr…
A Schur Complement Cheeger Inequality
Aaron Schild
Cheeger's inequality shows that any undirected graph with minimum nonzero normalized Laplacian eigenvalue has a cut with conductance at most . Qualitativel…
Spectral Subspace Sparsification
Huan Li, Aaron Schild
We introduce a new approach to spectral sparsification that approximates the quadratic form of the pseudoinverse of a graph Laplacian restricted to a subspace. We show that sparsif…
An almost-linear time algorithm for uniform random spanning tree generation
Aaron Schild
We give an -time algorithm for generating a uniformly random spanning tree in an undirected, weighted graph with max-to-min weight ratio . We also give an $m…
Localization of Electrical Flows
Aaron Schild, Satish Rao, Nikhil Srivastava
We show that in any graph, the average length of a flow path in an electrical flow between the endpoints of a random edge is . This is a consequence of a more general…
Interdiction Problems on Planar Graphs
Feng Pan, Aaron Schild
Interdiction problems are leader-follower games in which the leader is allowed to delete a certain number of edges from the graph in order to maximally impede the follower, who is…