{"id":"arxiv/2610.18328","url":"https://arxiv.org/abs/2610.18328","tags":["cs.DS","cs.DM","math.OC"],"score":0,"title":"A Practical Combinatorial Interior Point Method for Minimum-Cost Flow","domain":"cs.DS","source":"arxiv","authors":["Emil Schätzle","Simon Meierhans","Rasmus Kyng","Maximilian Probst Gutenberg"],"reviews":0,"subject":"cs.DS","summary":"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 recursive data structures, large constants and multiple log factors. In this paper, we give an implementation following the core ideas of their IPM with practical data structures and empirically obtained decision rules. We compare our solver with the cost scaling and network…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-13","reactions":{}}