用预测值加速网络流算法，实测提速超12倍
Minimum-Cost Network Flow with Dual Predictions
- 基于ε-松弛法，引入对偶预测优化求解过程
- 理论证明预测误差越小，算法越快，实际提速12.74倍
- 适用于交通网络与芯片布线等大规模优化场景
近期研究显示机器学习预测可显著提升经典算法性能。本文首次提出一种融合对偶预测的最小费用网络流算法，基于经典的ε-松弛法。我们给出了以无穷范数预测误差为参数的时间复杂度上界，该上界具有一致性和鲁棒性。同时，我们证明了在PAC学习框架下预测模型的样本复杂度。我们在两个最小费用流应用中验证了理论结果：一是交通网络，二是芯片逃逸布线。前者采用固定预测，后者使用基于特征的神经网络模型进行预测推断。实验表明，在两项任务中分别实现平均12.74倍和1.64倍的加速。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。