21 citations · 33 across the 12 of their papers we have counts for
4 papers · 2 filters
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…