Improving Max Flow
Photo: Graphic: Christine Daniloff
November 9, 2010
For years computer scientists approached the maximum-flow (max flow) problem, the greatest amount of data that can be sent across a specific network, using a tried-and-true method: Graphs that depict a network’s maximum capacity. The graphs allowed users to search for the most efficient mode of delivering information and proved useful in a variety of fields, from network analysis to digital image processing, airline scheduling and more.
Now CSAIL Professor Jonathon Kelner, along with CSAIL graduate student Aleksander Madry, undergraduate student Paul Christiano and Professors Daniel Spielman of Yale and Shanghua Teng of USC, have updated the max flow algorithm for the first time in 10 years. By representing max flow as a matrix instead of a graph, Kelner and his team have created a system that can solve the max flow problem in a much quicker and more efficient manner than the traditional graph.
Kelner’s colleagues believe the matrix approach to max flow should spur additional research and development in the field for years to come.
Learn more about Kelner’s work with max flow here.