Predictive Flows for Faster Ford-Fulkerson
Predictive Flows for Faster Ford-Fulkerson
复制标题
DOI：
10.48550/arxiv.2303.00837
复制
发表时间：
2023-03
期刊：
影响因子：
--
通讯作者：
Sami Davies;Benjamin Moseley;Sergei Vassilvitskii;Yuyan Wang
中科院分区：
文献类型：
--
作者：
Sami Davies;Benjamin Moseley;Sergei Vassilvitskii;Yuyan Wang
近期研究表明，利用已学习到的预测结果，能够缩短二分匹配及类似组合问题算法的运行时间。在本研究中，我们基于这一思路，通过将预测流作为初始值输入福特 - 富尔克森（Ford - Fulkerson）算法，来提升这一广泛应用于计算最大流的算法的性能。就预测质量而言，我们提出的方法具备强大的理论性能。随后，我们考虑了图像分割这一计算机视觉中流的常见应用场景，并以有力的实证结果对理论分析加以补充。
Recent work has shown that leveraging learned predictions can improve the running time of algorithms for bipartite matching and similar combinatorial problems. In this work, we build on this idea to improve the performance of the widely used Ford-Fulkerson algorithm for computing maximum flows by seeding Ford-Fulkerson with predicted flows. Our proposed method offers strong theoretical performance in terms of the quality of the prediction. We then consider image segmentation, a common use-case of flows in computer vision, and complement our theoretical analysis with strong empirical results.