21 citations · 33 across the 12 of their papers we have counts for
16 papers
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…
Dynamic Connectivity, Minimum Spanning Tree, and 2-Edge Connectivity with Polylogarithmic Worst-Case Update Time
Simon Meierhans, Maximilian Probst Gutenberg, Yu-Cheng Yeh
We give fully dynamic algorithms for maintaining connectivity, minimum spanning tree, and -edge connectivity of a graph with worst-case polylogarithmic update time. Our algorith…
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…
An Approximation Algorithm for Graph Label Selection
Josia John, Simon Meierhans, Maximilian Probst Gutenberg
In the graph label selection problem, one is given an -vertex graph and a budget , and seeks to select vertices whose labels enable accurate prediction of the labels on t…
Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
Simon Meierhans, Maximilian Probst Gutenberg
Whether a graph is connected is arguably its most fundamental property. Naturally, connectivity was the first characteristic studied for dynamic graphs, i.e. graphs that…
Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
Simon Meierhans, Maximilian Probst Gutenberg, Thatchaphol Saranurak
Expander graphs are known to be robust to edge deletions in the following sense: for any online sequence of edge deletions to an -edge graph that is…
Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
Daoyuan Chen, Simon Meierhans, Maximilian Probst Gutenberg +1
Expander decompositions have become one of the central frameworks in the design of fast algorithms. For an undirected graph , a near-optimal -expander decomposition is…
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 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 -approximate spanner of a graph with vertices as 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 still exists in a directed graph, with edge costs and capacities, undergoing decreme…
Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, - 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, - shortest pat…
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 -edge graph undergoing edge inse…
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…
Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg
Given a directed, weighted graph undergoing edge insertions, the incremental single-source shortest paths (SSSP) problem asks for the maintenance of approximate distances…
Content Adaptive Optimization for Neural Image Compression
Joaquim Campos, Simon Meierhans, Abdelaziz Djelouah +1
The field of neural image compression has witnessed exciting progress as recently proposed architectures already surpass the established transform coding based approaches. While, s…
Transformations of High-Level Synthesis Codes for High-Performance Computing
Johannes de Fine Licht, Maciej Besta, Simon Meierhans +1
Spatial computing architectures promise a major stride in performance and energy efficiency over the traditional load/store devices currently employed in large scale computing syst…