The MIT public relations office is reporting a new result on the maximum flow problem. It appears that work by Kelner, Madry, Christiano, Spielman and Teng (in some permutation: not surprisingly, the MIT release stresses the MIT authors) has reduced the complexity of maxflow to (V+E)^4/3 (from (V+E)^3/2. Details are pretty sketchy, but the approach seems to use matrix operations instead of the more combinatorial “push flow along this path (or edge)”. From the announcement:
Traditionally, Kelner explains, algorithms for calculating max flow would consider one path through the graph at a time. If it had unused capacity, the algorithm would simply send more stuff over it and see what happened. Improvements in the algorithms’ efficiency came from cleverer and cleverer ways of selecting the order in which the paths were explored.
But Kelner, CSAIL grad student Aleksander Madry, math undergrad Paul Christiano, and Professors Daniel Spielman and Shanghua Teng of, respectively, Yale and USC, have taken a fundamentally new approach to the problem. They represent the graph as a matrix, which is math-speak for a big grid of numbers. Each node in the graph is assigned one row and one column of the matrix; the number where a row and a column intersect represents the amount of stuff that may be transferred between two nodes.In the branch of mathematics known as linear algebra, a row of a matrix can also be interpreted as a mathematical equation, and the tools of linear algebra enable the simultaneous solution of all the equations embodied by all of a matrix’s rows. By repeatedly modifying the numbers in the matrix and re-solving the equations, the researchers effectively evaluate the whole graph at once.
I am a little hesitant here, since I can’t find the relevant paper. Worse, the presentation abstract talks about approximate maximum flow (see the September 28 entry at the MIT seminar listing), which would then add in some extra terms for exact max flow. So I welcome more information on the result.
In any case, it is exciting to see a new approach to these sorts of problems. If past experience is any guide, if this approach is workable, we can expect to see an avalanche of papers applying the approach to all sorts of network flow problems: shortest path, min cost flow, generalized networks (with multipliers) and so on. A likely good place to start is this overview paper by Spielman.
It’s definitely an epsilon-approximate algorithm that runs in time polynomial in 1/epsilon and the size of the graph.
The overview paper by Spielman seems to explain the various ingredients in their approach. Just looking at the paper, I’m interested in the work because it has a very different feel from classical combinatorial approaches to max-flow. On the other hand, it isn’t clear yet that the new algorithm will be practically useful.
The accompanying paper by Spielman et al. (called “Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs”) introducing the new approach to max flow has been posted to arXiv: http://arxiv.org/abs/1010.2921
The abstract says: “We introduce a new approach to computing an *approximately* maximum s-t flow in a capacitated, undirected graph. This flow is computed by solving a sequence of electrical flow problems. Each electrical flow is given by the solution of a system of linear equations in a Laplacian matrix, and thus may be approximately computed in nearly-linear time.
Using this approach, we develop the fastest known algorithm for computing approximately maximum s-t flows. For a graph having n vertices and m edges, our algorithm computes a (1-\epsilon)-approximately maximum s-t flow in time \tilde{O}(m^{4/3} \epsilon^{-3}). A dual version of our approach computes a (1+\epsilon)-approximately minimum s-t cut in time \tilde{O}(m+n^{4/3}\eps^{-8/3}), which is the fastest known algorithm for this problem as well. Previously, the best dependence on m and n was achieved by the algorithm of Goldberg and Rao (J. ACM 1998), which can be used to compute approximately maximum s-t flows in time \tilde{O (\min(m^{3/2},mn^{2/3})), and approximately minimum s-t cuts in time \tilde{O}(m+n^{3/2}\epsilon^{-3}).”