Research map / Learning theory and algorithms / Combinatorial and search optimization
Warm-starting Push-Relabel
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives the first theoretical guarantees for warm-starting Push-Relabel from an arbitrary predicted pseudo-flow, with runtime O(eta·n^2) where eta is the prediction error, and validates it on image segmentation max-flow sequences.
Problem
Max-flow/min-cut with predicted flows: Push-Relabel normally requires a cut-saturating pre-flow start, so it is unclear how to warm-start it from an arbitrary pseudo-flow and what running-time guarantee holds.
Approach
Uses the gap relabeling heuristic to maintain a cut whose t-side is monotonically decreasing, enabling a three-phase warm-start (saturate a cut, swap excess/deficit across the cut via auxiliary max-flows, then finish) with running time bounded by the prediction error rather than the graph size.
Key results
- Warm-start Push-Relabel on 480x480 Shoe images runs in 364.42 s versus 756.77 s cold-start (about 52% savings).
- Warm-start Push-Relabel on 120x120 Shoe images runs in 3.74 s versus 6.44 s cold-start, while Ford-Fulkerson cold-start exceeds 1 hour at 480x480.
- Warm-start Push-Relabel is slightly slower than cold-start on some small instances (e.g., Dog 60x60: 0.95 s vs 0.76 s).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Warm-start Push-Relabel using the previous image's optimal flow and cut instead of cold-starting | Push-Relabel · Birdhouse image segmentation, 120×120 and 480×480 | runtime (s): 5.42 -> 4.98; 604.54 -> 502.58 | Mixed |
| Warm-start Push-Relabel using the previous image's optimal flow and cut instead of cold-starting | Push-Relabel · Head image segmentation, 120×120 and 480×480 | runtime (s): 5.90 -> 5.92; 365.25 -> 285.75 | Mixed |
| Warm-start Push-Relabel using the previous image's optimal flow and cut instead of cold-starting | Push-Relabel · Shoe image segmentation, 120×120 and 480×480 | runtime (s): 6.44 -> 3.74; 756.77 -> 364.42 | Helped |
| Warm-start Push-Relabel using the previous image's optimal flow and cut instead of cold-starting | Push-Relabel · Dog image segmentation, 120×120 and 480×480 | runtime (s): 6.76 -> 6.38; 834.63 -> 363.41 | Helped |
Surprising findings
- Warm-start Push-Relabel is slightly slower than cold-start on small images, with savings appearing only as image size grows.
- Phase one (finding a cut-saturating pseudo-flow) dominates runtime, though fixing the wrong-side excesses and deficits is cheap.
Limitations
- Experiments are limited to image segmentation max-flow instances on a single image family.
- Warm-start gains are small or negative on small images, and the theory bound O(eta·n^2) is not always better in practice than Ford-Fulkerson warm-start bounds.
- Some implementation choices for projecting the old flow to a cut-saturating one are heuristic rather than covered by theory.
Experimental setup
Datasets: Pattern Recognition and Image Processing dataset (University of Freiburg) Image Sequences Stereo Ego-Motion dataset (University of Freiburg)
Benchmarks: image segmentation max-flow instances (Birdhouse, Head, Shoe, Dog) at sizes 30x30 to 480x480
Metrics: average running time (s)
Baselines: Ford-Fulkerson (cold-start) Ford-Fulkerson (warm-start) Push-Relabel (cold-start)
Builds on: Push-Relabel gap relabeling heuristic Ford-Fulkerson warm-start with predictions (Edmonds-Karp) Davies et al. pseudo-flow lemma
Closest papers by meaning
- Bellman Optimal Stepsize Straightening of Flow-Matching Models (ICLR 2024 · similarity 0.82)
- RepAn: Enhanced Annealing through Re-parameterization (CVPR 2024 · similarity 0.82)
- Shortcutting Pre-trained Flow Matching Diffusion Models is Almost Free Lunch (NeurIPS 2025 · similarity 0.82)
- Rectified Diffusion: Straightness Is Not Your Need in Rectified Flow (ICLR 2025 · similarity 0.82)
- Context-Aware Iteration Policy Network for Efficient Optical Flow Estimation (AAAI 2024 · similarity 0.81)
- ProReflow: Progressive Reflow with Decomposed Velocity (CVPR 2025 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.