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…