Li and Wice reach near-linear max flow without IPM outer loop
TL;DR
- Jason Li and Alex Wice describe an m^{1+o(1)}-time maximum flow algorithm that avoids the interior-point method framework used by recent almost-linear-time results.
- The construction hinges on the balancing weights technique of Li (2026) producing an approximate pseudo-circulation of a directed, capacitated graph directly.
- The reference points named in the abstract are Chen et al. (FOCS 2022) and van den Brand et al. (FOCS 2024).
Two researchers claim they can compute maximum flow in near-linear time without the interior-point machinery that powered the recent breakthroughs on the problem.
In a nine-page arXiv preprint posted August 18, Jason Li and Alex Wice show that "the balancing weights technique of Li (2026) actually produces an approximate pseudo-circulation of a directed, capacitated graph in m^{1+o(1)} time." Together with standard flow techniques, that yields a max-flow algorithm that "avoids the interior-point method framework of recent almost-linear time algorithms," which the authors attribute to Chen et al. (FOCS 2022) and van den Brand et al. (FOCS 2024).
The headline complexity is not an improvement on those earlier almost-linear-time results. What changes is the route: pseudo-circulations produced directly by balancing weights, without the outer IPM loop.
Two experts in our Who's Who directory shared the paper the day it appeared.
Shared on Bluesky by 2 AI experts
-
Another amazing result by Jason Li: an almost linear-time algorithm for maximum flows on capacitated directed graphs, avoiding the interior-point approach behind many of the recent max-flow results. arxiv.org/abs/2608.…
View on Bluesky →
Originally reported by arxiv.org
Read the original article →Original headline: Maximum Flow Without the Outer IPM