Minimum-Cost Network Flow with Dual Predictions
This work addresses the challenge of enhancing computational efficiency in network flow problems for applications like traffic management and chip design, though it is incremental as it builds on existing algorithms.
The paper tackles the problem of improving classic minimum-cost network flow algorithms by incorporating machine-learned dual predictions, resulting in average speedups of 12.74× and 1.64× on traffic networks and chip escape routing applications.
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\times$ and $1.64\times$ average speedup on two applications.