Preprint
Oct 2026
A Practical Combinatorial Interior Point Method for Minimum-Cost Flow
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 approach uses an Interior Point Method (IPM) to achieve complexity $m^{1+o(1)}\log U \log C$. However, the $m^{1+o(1)}$ factor hides intricate r...
Emil Schätzle, Simon Meierhans, Rasmus Kyng et al.
· 1 citation