Fast Flow Algorithms via Cut-Approximators
summary
Claims a nearly-linear M^{1+o(1)} randomized algorithm for approximate undirected max‑flow by reducing flow construction to checking a compact cut-approximator; gives an iterative subroutine almost route that either returns a violating cut or a flow meeting capacities whose residual is small on every approximator cut. Recursing with capacities scaled by ε routes the remainder. Key tools: Madry‑style N^{1+o(1)} cut families, ~α^2/ε^2 · log M iterations, per‑iteration linear work plus cut checks, greedy per‑edge pushes and a prices/gradient (multiplicative‑weights) update.
AI-written summary · about