EUVIMEDEUVIMED entdecken
Crossref

Minimum-Cost Network Flow with Dual Predictions

Zhiyang Chen, Hailong Yao, Xia Yin

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →