arXiv preprint ·
A Practical Combinatorial Interior Point Method for Minimum-Cost Flow
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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 simplex solvers of LEMON on the instance families of the DIMACS Flow Challenge 2.0 core benchmark. Our implementation scales competitively on five of twelve families and better on two. On grid_wide we observe close to linear scaling: $m^{1.04}$ against $m^{1.48}$ for LEMON. We read these results as first evidence that the almost-linear-time framework can be relevant in practice, discuss our insights gained during the implementation process, and motivate where future work should focus to bridge the theory-practice gap.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.