Rasmus Kyng

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…

math.NA2026

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…

cs.DS2025

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…

cs.DS2025

A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows

Maximilian Probst Gutenberg, Rasmus Kyng, Weixuan Yuan +1

Given an undirected graph $G = (V, E, w)$ , a Gomory-Hu tree $T$ (Gomory and Hu, 1961) is a tree on $V$ that preserves all-pairs mincuts of $G$ exactly. We present a simple, efficient r…

cs.DS2025

Deterministic Almost-Linear-Time Gomory-Hu Trees

Amir Abboud, Rasmus Kyng, Jason Li +5

Given an $m$ -edge, undirected, weighted graph $G = (V, E, w)$ , a Gomory-Hu tree $T$ (Gomory and Hu, 1961) is a tree over the vertex set $V$ such that all-pairs mincuts in $G$ are prese…

Acceleration Meets Inverse Maintenance: Faster $ℓ_{\infty}$ -Regression

Deeksha Adil, Shunhua Jiang, Rasmus Kyng

We propose a randomized multiplicative weight update (MWU) algorithm for $ℓ_{\infty}$ regression that runs in $O (n^{2 + 1/22.5} poly (1/ ε))$ time when…

Bootstrapping Dynamic APSP via Sparsification

Rasmus Kyng, Simon Meierhans, Gernot Zöcklein

We give a simple algorithm for the dynamic approximate All-Pairs Shortest Paths (APSP) problem. Given a graph $G = (V, E, l)$ with polynomially bounded edge lengths, our data struc…

A Simple Dynamic Spanner via APSP

Rasmus Kyng, Simon Meierhans, Gernot Zöcklein

We give a simple algorithm for maintaining a $n^{o (1)}$ -approximate spanner $H$ of a graph $G$ with $n$ vertices as $G$ receives edge updates by reduction to the dynamic All-Pairs…

Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality

Jan van den Brand, Li Chen, Rasmus Kyng +4

We give the first almost-linear total time algorithm for deciding if a flow of cost at most $F$ still exists in a directed graph, with edge costs and capacities, undergoing decreme…

Optimal Electrical Oblivious Routing on Expanders

Cella Florescu, Rasmus Kyng, Maximilian Probst Gutenberg +1

In this paper, we investigate the question of whether the electrical flow routing is a good oblivious routing scheme on an $m$ -edge graph $G = (V, E)$ that is a $Φ$ -expander, i.e.…

cs.DS2023

Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, $s$ - $t$ Shortest Path, and Minimum-Cost Flow

Li Chen, Rasmus Kyng, Yang P. Liu +2

We give the first almost-linear time algorithms for several problems in incremental graphs including cycle detection, strongly connected component maintenance, $s$ - $t$ shortest pat…

cs.DS2023★ 1 cited

A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and their Applications

Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg

We present a general toolbox, based on new vertex sparsifiers, for designing data structures to maintain shortest paths in dynamic graphs. In an $m$ -edge graph undergoing edge inse…

cs.DS2023

Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time

Jan van den Brand, Li Chen, Rasmus Kyng +5

We provide an algorithm which, with high probability, maintains a $(1 - ε)$ -approximate maximum flow on an undirected graph undergoing $m$ -edge additions in amortized $m^{o(1)} ε^{-3…

cs.DS2023★ 3 cited

A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow

Jan van den Brand, Li Chen, Rasmus Kyng +5

We give a deterministic $m^{1 + o (1)}$ time algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with $m$ edges and polynomially bounded integral dem…

Fast Algorithms for $ℓ_{p}$ -Regression

Deeksha Adil, Rasmus Kyng, Richard Peng +1

The $ℓ_{p}$ -norm regression problem is a classic problem in optimization with wide ranging applications in machine learning and theoretical computer science. The goal is to comput…

A Simple Framework for Finding Balanced Sparse Cuts via APSP

Li Chen, Rasmus Kyng, Maximilian Probst Gutenberg +1

We present a very simple and intuitive algorithm to find balanced sparse cuts in a graph via shortest-paths. Our algorithm combines a new multiplicative-weights framework for solvi…

Derandomizing Directed Random Walks in Almost-Linear Time

Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg

In this article, we present the first deterministic directed Laplacian L systems solver that runs in time almost-linear in the number of non-zero entries of L. Previous reductions…

cs.DS2022★ 12 cited

Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

Li Chen, Rasmus Kyng, Yang P. Liu +3

We give an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with $m$ edges and polynomially bounded integral demands, costs, and capacities in…