Blog: First Improvement of Fundamental Algorithm in 10 Years

First Improvement of Fundamental Algorithm in 10 Years
MIT News (09/27/10) Larry Hardesty

Massachusetts Institute of Technology (MIT) researchers, in collaboration with colleagues at Yale University and the University of Southern California, have demonstrated the first improvement to the maximum-flow (max flow) algorithm in 10 years. The max flow problem calculates the maximum amount of data that can move from one end of a network to another, considering the capacity limitations of the network's links. The researchers' new approach represents a network's graph as a matrix. Each node in the graph is assigned one row and one column of the matrix, with the intersections representing the amount of data that may be transferred between two nodes. The researchers can evaluate the whole graph at once by repeatedly modifying the numbers in the matrix and resolving the equations. "My guess is that this particular framework is going to be applicable to a wide range of other problems," says Cornell University professor John Hopcroft, co-recipient of the 1986 A.M. Turing Award. "When there's a breakthrough of that nature, usually, then, a subdiscipline forms, and in four or five years, a number of results come out."

View Full Article