Source-linked AI summary
Nearly Maximum Flows in Nearly Linear Time
Jonah Sherman
TL;DR
The paper addresses how to compute near-optimal single-commodity flows in undirected capacitated graphs efficiently. It introduces congestion approximators and an iterative potential-minimization method that tolerates residual demands. The resulting algorithms compute (1 + ε)-approximate minimum-congestion flows in nearly linear time, with a simpler conductance-dependent bound for suitable graphs.
Problem
The paper studies efficient minimum-congestion routing for single-commodity demands in undirected capacitated graphs, a formulation equivalent to maximum flow.
Method
The algorithm minimizes current congestion plus an overestimate of residual-routing cost using an α-congestion-approximator, while allowing temporary flow-conservation errors.
Results
(1 + ε)-approximate minimum-congestion flows are computable in mε^-2 · exp(˜O(√log n)) time, and in ˜O(mφ^-1) time for graphs of conductance φ.
Takeaways & Limitations
Nearly linear-time construction and application of congestion approximators yields nearly linear-time near-optimal flows, with especially simple algorithms available for some graph classes.
Takeaways & Limitations
The preliminary draft proves the key iteration theorem with weaker ˜O(α^2ε^-3 log^2(n)) parameters, while the improved bounds require accelerated gradient methods; further simplification may also be possible.
Abstract
from arXiv · showhide
We introduce a new approach to the maximum flow problem in undirected, capacitated graphs using $α$-\emph{congestion-approximators}: easy-to-compute functions that approximate the congestion required to route single-commodity demands in a graph to within a factor of $α$. Our algorithm maintains an arbitrary flow that may have some residual excess and deficits, while taking steps to minimize a potential function measuring the congestion of the current flow plus an over-estimate of the congestion required to route the residual demand. Since the residual term over-estimates, the descent process gradually moves the contribution to our potential function from the residual term to the congestion term, eventually achieving a flow routing the desired demands with nearly minimal congestion after $\tilde{O}(α\eps^{-2}\log^2 n)$ iterations. Our approach is similar in spirit to that used by Spielman and Teng (STOC 2004) for solving Laplacian systems, and we summarize our approach as trying to do for $\ell_\infty$-flows what they do for $\ell_2$-flows. Together with a nearly linear time construction of a $n^{o(1)}$-congestion-approximator, we obtain $1+\eps$-optimal single-commodity flows undirected graphs in time $m^{1+o(1)}\eps^{-2}$, yielding the fastest known algorithm for that problem. Our requirements of a congestion-approximator are quite low, suggesting even faster and simpler algorithms for certain classes of graphs. For example, an $α$-competitive oblivious routing tree meets our definition, \emph{even without knowing how to route the tree back in the graph}. For graphs of conductance $φ$, a trivial $φ^{-1}$-congestion-approximator gives an extremely simple algorithm for finding $1+\eps$-optimal-flows in time $\tilde{O}(mφ^{-1})$.
1 Introduction
The paper develops a congestion-approximator framework for nearly linear-time minimum-congestion flows in undirected graphs. It combines iterative potential minimization with efficiently constructible approximators, obtaining near-optimal flows and faster specialized algorithms.
- 1 Introduction: The minimum-congestion formulation routes a demand vector while minimizing the maximum edge congestion, equivalently capturing maximum s-t flow.For unit s-t flow, minimum congestion equals the reciprocal of the maximum flow with congestion one.
- 1 Introduction: The algorithm permits residual excesses and deficits, minimizing current congestion plus an overestimate of the cost of routing the residual demand.Overestimating residual-routing cost encourages the process to eliminate residuals while allowing larger iterative steps.
- 1 Introduction: An α-congestion-approximator enables near-optimal flows after ˜O(αε^-2 log^2(n)) iterations, with O(m) work per iteration plus applications of R and R⊤.The returned flow satisfies Bf = b and has congestion at most (1 + ε)bS/cS for the reported cut S.
- 1 Introduction: The framework parallels Spielman and Teng’s ℓ2-flow approach while directly targeting ℓ∞ congestion through approximators and a congestion potential.The paper relates spanning-tree and conductance approximators to corresponding simple cases in the Laplacian-solving approach.
- 1 Introduction: The resulting algorithm computes (1 + ε)-approximate minimum-congestion flows in mε^-2 · exp(˜O(√log n)) time, or ˜O(mφ^-1) for graphs of conductance φ.The general result follows by combining the approximator construction with the flow algorithm; the conductance result uses a degree-based approximator.
2 Congestion Potential
The approach minimizes a potential combining current edge congestion with an over-estimate of the congestion needed to route residual demands. Softmax-based descent and repeated residual routing yield near-optimal flows using a congestion-approximator.
- Potential function: The potential function combines current congestion with an over-estimate of the cost of routing residual demands.This transforms the constrained routing problem into unconstrained optimization while allowing intermediate flows that do not exactly conserve demands.
- Potential function: Softmax approximates the infinity norm, enabling nearly optimal minimization of the potential through gradient-based steps.The gradient is accurate in the region where steps have ℓ∞-norm O(1), and the congestion-approximator permits edge steps of size Ω(α^-1)c_e.
- AlmostRoute: Theorem 2.1 gives AlmostRoute a bound of ˜O(αε^-2 log n) iterations for producing a flow and cut.Each iteration requires O(m) time plus multiplications by R and R⊤.
- Residual routing: A nearly optimal intermediate flow leaves residual routing cost at most ε∥Rb∥∞, allowing the remaining residual to be handled iteratively.The residual bound follows from the potential’s factor-two slack and a congestion-approximating routing for the residual.
- Residual routing: Repeatedly applying AlmostRoute to residual demands and routing the final residual on a spanning tree completes an exact routing of b.The procedure uses T = log(2m) residual calls before the final spanning-tree routing.
- Convergence analysis: The preliminary draft proves weaker ˜O(α^2ε^-3 log^2(n)) parameters with naive steepest descent, while improved parameters require accelerated gradient.The draft’s iteration analysis bounds steps between scaling phases by O(α^2ε^-3 log n).
3 Computing Congestion-Approximators
The section constructs congestion-approximators recursively from sparsified distributions of j-trees, then shows how to apply the resulting matrix and its transpose efficiently. The construction dominates cuts, supports low-congestion routing, and runs in nearly linear time for suitable parameters.
- Construction: A j-tree combines a forest with j components and a core graph connecting one representative vertex from each component.The forest and core decomposition is the structural basis for the recursive construction.
- Guarantees: Each constructed Gi dominates G on all cuts, while the weighted combination of the Gi can be routed in G with congestion ˜O(log n).The distribution of t graphs is obtained in ˜O(tm) time, and the cut-dominance property is used in the approximator analysis.
- Construction: The construction recursively applies Madry’s j-tree distribution to sparsified cores, using ComputeTrees(Sparsify(G, 1), n1/k) at the top level.The resulting representation is a list of weighted forests and recursively constructed core data structures.
- Guarantees: ComputeTrees produces a data structure whose sampled trees dominate G on every cut and whose expected sampled tree is routable in G with congestion log(n)log(n)/log(t).Its construction time is ˜O(tn), and the associated matrix R has ˜O(tn) rows.
- Approximator: The matrix R is an α-congestion-approximator when the expected sampled tree is routable in G with congestion α.For any demand b, the infinity norm of Rb captures tree-edge congestion and yields an α-factor approximation to optimal routing congestion.
- Implementation: R and R⊤ are evaluated recursively using linear-time tree routines, giving total running time ˜O(tn) for both procedures.TreeFlow computes forest-edge flows, while TreePotential converts per-congestion prices into vertex potentials.
4 Final Remarks
The final remarks identify alternative congestion-approximators and possible simplifications. Oblivious routing trees require only the tree itself, while further simplification may be possible using prior work on the Spielman–Teng algorithm.
- Alternative approximators: An α-competitive oblivious routing tree supplies a log(n)O(1)-congestion-approximator through its single-edge cuts.The flow algorithm needs the tree, not the routings of the tree back in the original graph.
- Alternative approximators: A nearly-linear-time algorithm for computing such a single tree would make it an ideal candidate for the flow algorithm.The existing oblivious routing schemes cited in the passage require polynomial time to compute.
- Future simplifications: Prior work substantially simplifies Spielman and Teng’s original algorithm, suggesting that the presented algorithm may also admit further simplification.
A Fixing Theorem 3.2
This appendix removes the capacity-ratio dependence in the j-tree construction by modifying edge lengths before computing small-stretch spanning trees. The modified lengths preserve the relevant bound up to a factor of two while limiting tree-edge congestion.
- Original analysis: SmallStretchTree repeatedly returns a spanning tree T whose path lengths are controlled by the maintained edge-length function l(e).The analysis normalizes the lengths so that the capacity-weighted total length is m.
- Capacity-ratio fix: The capacity-ratio dependence arises because the tree can contain many different congestion scales.
- Capacity-ratio fix: Computing a small-stretch tree with respect to l′ preserves equation (8) with an extra factor of two and ensures no tree edge has congestion above ˜O(m).