A Practical Combinatorial Interior Point Method for Minimum-Cost Flow

Emil Schätzle, Simon Meierhans, Rasmus Kyng, Maximilian Probst Gutenberg

arXivarxiv/2610.18328Oct 13, 2026cs.DSscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2610.18328
curl -X POST /api/v1/records/arxiv/2610.18328/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.18328/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'