Predictive Flows for Faster Ford-Fulkerson

Sami Davies, Benjamin Moseley, Sergei Vassilvitskii, Yuyan Wang
3/1/2023

No confident code implementation found for this paper.

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.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Graph Neural Network-Informed Predictive Flows for Faster Ford-Fulkerson and PAC-Learnability

87% match2026

Learning-Augmented Maximum Flow

87% match2022

Smart-GRPO: Smartly Sampling Noise for Efficient RL of Flow-Matching Models

81% match2025

Rethinking Warm-Starts with Predictions: Learning Predictions Close to Sets of Optimal Solutions for Faster L-/L♮-Convex Function Minimization

81% match2023

Flow Priors for Linear Inverse Problems via Iterative Corrupted Trajectory Matching

79% match1 repo272024

Flow Priors for Linear Inverse Problems via Iterative Corrupted Trajectory Matching

79% match1 repo272024

Cite this paper

@article{davies2023predictive,
  title  = {Predictive Flows for Faster Ford-Fulkerson},
  author = {Sami Davies and Benjamin Moseley and Sergei Vassilvitskii and Yuyan Wang},
  year   = {2023},
  eprint = {2303.00837},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/pdf/2303.00837},
  journal = {ICML 2023 2023}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2303.00837.svg)](https://codeofpaper.com/paper/2303.00837)

Discussion