Minimum-Cost Network Flow with Dual Predictions
Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (43) · 36820-36828
DOI: 10.1609/aaai.v40i43.41008 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Zhiyang Chen und 2 weiteren Autor:innen.
Abstract (Originalsprache)
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 ε-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.
Zitieren
APA
Chen, Z., Yao, H., & Yin, X. (2026). Minimum-Cost Network Flow with Dual Predictions. Proceedings of the AAAI Conference on Artificial Intelligence, 40(43), 36820-36828. https://doi.org/10.1609/aaai.v40i43.41008
Vancouver
Chen Z, Yao H, Yin X. Minimum-Cost Network Flow with Dual Predictions. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(43):36820-36828. doi:10.1609/aaai.v40i43.41008
BibTeX
@article{Chen2026,
author = {Chen, Zhiyang and Yao, Hailong and Yin, Xia},
title = {Minimum-Cost Network Flow with Dual Predictions},
journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
year = {2026},
volume = {40},
number = {43},
pages = {36820--36828},
doi = {10.1609/aaai.v40i43.41008}
}
EUVIMED