10 papers · 1 filter
Partially-Dynamic All-Pairs Maxflow and Effective Resistance via Stable Sparsifiers
Gramoz Goranci, Rasmus Kyng, Maximilian Probst Gutenberg +2
We give a randomized data structure for undirected weighted graphs that are partially dynamic, i.e., that undergo either only edge insertions or only edge deletions. The data struc…
An Online Sparsification Algorithm from the Book
Gramoz Goranci, Rasmus Kyng, Maximilian Probst Gutenberg +2
In their seminal paper [Cohen et al., 2016], Cohen, Musco, and Pachocki proposed a natural and simple online spectral sparsification algorithm: rows $a_1, a_2, \ldots \in \mathbb{R…
A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows
Maximilian Probst Gutenberg, Rasmus Kyng, Weixuan Yuan +1
Given an undirected graph , a Gomory-Hu tree (Gomory and Hu, 1961) is a tree on that preserves all-pairs mincuts of exactly. We present a simple, efficient r…
Random-Shift Revisited: Tight Approximations for Tree Embeddings and L1-Oblivious Routings
Rasmus Kyng, Maximilian Probst Gutenberg, Tim Rieder
We present a new and surprisingly simple analysis of random-shift decompositions -- originally proposed by Miller, Peng, and Xu [SPAA'13]: We show that decompositions for exponenti…
Deterministic Almost-Linear-Time Gomory-Hu Trees
Amir Abboud, Rasmus Kyng, Jason Li +5
Given an -edge, undirected, weighted graph , a Gomory-Hu tree (Gomory and Hu, 1961) is a tree over the vertex set such that all-pairs mincuts in are prese…
Acceleration Meets Inverse Maintenance: Faster -Regression
Deeksha Adil, Shunhua Jiang, Rasmus Kyng
We propose a randomized multiplicative weight update (MWU) algorithm for regression that runs in time whe…