An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicom...
summary
Presents an algorithm that computes a (1 − ε)-approximate max flow in undirected graphs in almost-linear time (m^{1+o(1)}), and extends to multi-commodity cases with polynomial dependence on k and 1/ε. Key ingredients are L_infty gradient descent (non‑Euclidean iterative method), oblique projection matrices that parametrize circulations, and constructive flow sparsifiers / recursive edge‑and‑vertex reductions that build a fast oblivious routing with competitive ratio m^{o(1)}. The pieces compose into a working procedure whose runtime and approximation guarantees beat the previous m^{4/3}‑type bounds.
AI-written summary · about