Faster Fundamental Graph Algorithms via Learned Predictions
Faster Fundamental Graph Algorithms via Learned Predictions
复制标题
DOI：
10.48550/arxiv.2204.12055
复制
发表时间：
2022-04
期刊：
影响因子：
--
通讯作者：
Justin Y. Chen;Sandeep Silwal;A. Vakilian;Fred Zhang
中科院分区：
文献类型：
--
作者：
Justin Y. Chen;Sandeep Silwal;A. Vakilian;Fred Zhang
我们考虑使用机器学习预测加速经典图形算法的问题。在此模型中，算法提供了从过去或类似实例中汲取的额外建议。考虑到其他信息，我们旨在改善传统的最差运行时间保证。我们的贡献如下：最后，我们提供了一组一般的可学习性定理，表明我们算法所需的预测可以有效地以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: 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.