7 papers
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…
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…