Predictive Flows for Faster Ford-Fulkerson

Sami Davies, Benjamin Moseley, Sergei Vassilvitskii, Yuyan Wang
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:7231-7248, 2023.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-davies23b, title = {Predictive Flows for Faster Ford-Fulkerson}, author = {Davies, Sami and Moseley, Benjamin and Vassilvitskii, Sergei and Wang, Yuyan}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {7231--7248}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/davies23b/davies23b.pdf}, url = {https://proceedings.mlr.press/v202/davies23b.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Predictive Flows for Faster Ford-Fulkerson %A Sami Davies %A Benjamin Moseley %A Sergei Vassilvitskii %A Yuyan Wang %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-davies23b %I PMLR %P 7231--7248 %U https://proceedings.mlr.press/v202/davies23b.html %V 202 %X 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.
APA
Davies, S., Moseley, B., Vassilvitskii, S. & Wang, Y.. (2023). Predictive Flows for Faster Ford-Fulkerson. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:7231-7248 Available from https://proceedings.mlr.press/v202/davies23b.html.

Related Material