Geometric convergence of widest-path augmentation
= Geometric convergence of widest-path augmentation
{title2=$F_k\leq(1-1/m)^k f^*$}
Starting from zero flow, a <widest augmenting path> increases the current flow by at least $F_k/m$, where $F_k$ is its remaining optimality gap. Therefore $F_{k+1}\leq(1-1/m)F_k$. Integer capacities keep this gap integer, so a gap below one is zero. The method takes $O(m\log f^*)$ augmentations for $f^*\geq2$, or uniformly $O(m\log(1+f^*))$; zero maximum flow requires no augmentation.