Showing 2018Show all
3 papers · 1 filter
cs.DS2018
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…
cs.DM2018
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…
cs.DS2018
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…