← Back to papers
2023 ICML ICML 2023

Predictive Flows for Faster Ford-Fulkerson

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.

🌉 Interdisciplinary Bridge — Computer Vision and Machine Learning
🐝 Cross-Pollinator — Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Healthcare & Medicine, Interdisciplinary, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Robotics, Speech & Audio

Authors

Sami Davies , Benjamin Moseley , Sergei Vassilvitskii , Yuyan Wang

Topics

Machine Learning > Optimization & Theory > Learning Theory Machine Learning > Optimization & Theory > Optimization Computer Vision > Processing > Image Segmentation

Keywords

image segmentation maximum flow flow network
Download PDF

Related papers

Orthogonality-Enforced Latent Space in Autoencoders: An Approach to Learning Disentangled Representations 2023
On the Convergence Rate of Gaussianization with Random Rotations 2023
Synthetic Prompting: Generating Chain-of-Thought Demonstrations for Large Language Models 2023
Generative Adversarial Symmetry Discovery 2023
Function-Space Regularization in Neural Networks: A Probabilistic Perspective 2023