24 citations · 59 across the 29 of their papers we have counts for
6 papers · 1 filter
A Practical Combinatorial Interior Point Method for Minimum-Cost Flow
Emil Schätzle, Simon Meierhans, Rasmus Kyng +1
In a recent breakthrough, Chen, Kyng, Liu, Peng, Probst Gutenberg, and Sachdeva (arXiv:2203.00671) designed the first almost-linear-time algorithm for minimum-cost flow. Their appr…
A Simpler and Faster Min-Cost Flow Solver via Min-Ratio Cycles from Distance Oracles
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg +1
The first almost-linear time maximum and minimum cost flow algorithm of Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva (FOCS 2022), reduced these flow objectives to a sequence of min…
VAC: A Volume-sampling-based Elimination Rule for Approximate Cholesky Factorization
Yves Baumann, Rasmus Kyng, Gernot Zöcklein
We propose Volume Appproximate Cholesky (VAC), an alternative sampling rule for practical approximate Cholesky algorithms. Our rule samples a uniformly random spanning tree of the…
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…
Linear Systems and Eigenvalue Problems: Open Questions from a Simons Workshop
Noah Amsel, Yves Baumann, Paul Beckman +33
This document presents a series of open questions arising in matrix computations, i.e., the numerical solution of linear algebra problems. It is a result of working groups at the w…