8 papers · 1 filter
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…
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…
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…