2013/10/01 by Jonah Sherman · 2 citations
Computer Science · Mathematics · #Stochastic Gradient Optimization Techniques #Markov Chains and Monte Carlo Methods #Complexity and Algorithms in Graphs #Computer science
paper · doi:10.1109/focs.2013.36
openalex publication_date 2013/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
We introduce a new approach to the maximum flow problem in undirected, capacitated graphs using congestion-approximators: easy-to-compute functions that approximate the congestion required to route single-commodity demands in a graph to within some factor α. 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 Õ(α2ε-2log2n) 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 ℓ∞-flows what they do for ℓ∞-flows. Together with a nearly linear time construction of a no(1)-congestion-approximator, we obtain 1 + ε-optimal singlecommodity flows undirected graphs in time m1+o(1)ε-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, even without knowing how to route the tree back in the graph. For graphs of conductance φ, a trivial φ-1-congestionapproximator gives an extremely simple algorithm for finding Õ(mφ-1).