论文标题
通过学习的预测更快的基本图算法
Faster Fundamental Graph Algorithms via Learned Predictions
论文作者
论文摘要
我们考虑使用机器学习预测加速经典图形算法的问题。在此模型中，算法提供了从过去或类似实例中汲取的额外建议。考虑到其他信息，我们旨在改善传统的最差运行时间保证。我们的贡献如下： （i）我们通过学习的双重匹配给出了最小的两分匹配算法，从而改善了Dinitz，IM，Lavastida，Moseley和Vassilvitskii的最新结果（Neurips，2021年）； （ii）我们将学习的双重方法扩展到单源的最短路径问题（负边长度），在足够准确的预测中实现了几乎线性的运行时，从而在戈德堡引起的经典最快算法上有所改善（Siam J. Comput。，1995）； （iii）我们为基于学习的图形算法提供了一个一般还原的框架，从而导致新算法受到学位约束子图和最低成本$ 0 $ 0 $ - $ 1 $流量，该算法是基于对双分支匹配的减少和最短路径问题的基础。 最后，我们提供了一组一般的可学习性定理，表明我们的算法所需的预测可以有效地以PAC方式学习。
We consider the question of speeding up classic graph algorithms with machine-learned predictions. In this model, algorithms are furnished with extra advice learned from past or similar instances. Given the additional information, we aim to improve upon the traditional worst-case run-time guarantees. Our contributions are the following: (i) We give a faster algorithm for minimum-weight bipartite matching via learned duals, improving the recent result by Dinitz, Im, Lavastida, Moseley and Vassilvitskii (NeurIPS, 2021); (ii) We extend the learned dual approach to the single-source shortest path problem (with negative edge lengths), achieving an almost linear runtime given sufficiently accurate predictions which improves upon the classic fastest algorithm due to Goldberg (SIAM J. Comput., 1995); (iii) We provide a general reduction-based framework for learning-based graph algorithms, leading to new algorithms for degree-constrained subgraph and minimum-cost $0$-$1$ flow, based on reductions to bipartite matching and the shortest path problem. Finally, we give a set of general learnability theorems, showing that the predictions required by our algorithms can be efficiently learned in a PAC fashion.
