# Minimum-Cost Network Flow with Dual Predictions

arXiv: https://arxiv.org/abs/2601.20203 · HTML: https://mlsanity.com/paper/2601.20203/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 35 references that are in the map.
- First posted on arXiv 28 Jan 2026.

## Builds on (most cited first, 12 of 12)

- [U-Net: Convolutional Networks for Biomedical Image Segmentation](https://mlsanity.com/paper/1505.04597/) (2015)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [A PAC Approach to Application-Specific Algorithm Selection](https://mlsanity.com/paper/1511.07147/) (2015)
- [Faster Matchings via Learned Duals](https://mlsanity.com/paper/2107.09770/) (2021)
- [Faster Fundamental Graph Algorithms via Learned Predictions](https://mlsanity.com/paper/2204.12055/) (2022)
- [Predictive Flows for Faster Ford-Fulkerson](https://mlsanity.com/paper/2303.00837/) (2023)
- [Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts](https://mlsanity.com/paper/2204.07312/) (2022)
- [Learning Complexity of Simulated Annealing](https://mlsanity.com/paper/2003.02981/) (2020)
- [Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cut](https://mlsanity.com/paper/2402.02328/) (2024)
- [Faster Global Minimum Cut with Predictions](https://mlsanity.com/paper/2503.05004/) (2025)
- [A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow](https://mlsanity.com/paper/2309.16629/) (2023)

## Abstract (arXiv)

Recent work has shown that machine-learned predictions can provably improve the performance of classic algorithms. In this work, we propose the first minimum-cost network flow algorithm augmented with a dual prediction. Our method is based on a classic minimum-cost flow algorithm, namely varepsilon-relaxation. We provide time complexity bounds in terms of the infinity norm prediction error, which is both consistent and robust. We also prove sample complexity bounds for PAC-learning the prediction. We empirically validate our theoretical results on two applications of minimum-cost flow, i.e., traffic networks and chip escape routing, in which we learn a fixed prediction, and a feature-based neural network model to infer the prediction, respectively. Experimental results illustrate 12.74× and 1.64× average speedup on two applications.