Reproduce “Warm-starting Push-Relabel” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Sami Davies, Sergei Vassilvitskii, Yuyan Wang
Researchers from UC Berkeley and Google Research developed a warm-start mechanism for the Push-Relabel algorithm, offering the first theoretical guarantees for its performance when initialized with a predicted pseudo-flow. The method achieves up to 2x speedups for image segmentation tasks on larger instances and provides a formal justification for the gap relabeling heuristic.
Key insights
- A new error metric, ", effectively quantifies the distance between a predicted pseudo-flow and an optimal flow, enabling tighter theoretical bounds for warm-starting.
- The research provides the first theoretical justification for the gap relabeling heuristic, demonstrating its efficiency by showing it maintains a shrinking set of nodes reachable to the sink.
- A key condition for a cut-saturating pseudo-flow to represent a minimum cut is established: all excess nodes must be on the source side and all deficit nodes on the sink side of the cut.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.