Hello,

We noticed you're browsing in private or incognito mode.

# Maximum Plus

## Classic logistics algorithm gets a makeover

The maximum-flow problem, or max flow, is one of the most basic problems in computer science: first solved during preparations for the Berlin airlift, it’s a component of many logistical problems and a staple of introductory courses on algorithms. Now MIT researchers, with colleagues at Yale and the University of Southern California, have demonstrated the first improvement of the algorithm in 10 years.

The max-flow problem is, roughly speaking, to calculate the maximum amount of “stuff” that can move from one end of a network to another, given the capacity limitations of the network’s links. The stuff could be data packets traveling over the Internet or boxes of goods traveling over the highways; the links’ limitations could be the bandwidth of Internet connections or the average traffic speeds on congested roads.

But the algorithm has applications outside network analysis, explains Jonathan Kelner, an assistant professor of applied mathematics at MIT, who helped lead the work. “A very, very large number of optimization problems, if you were to look at the fastest algorithm right now for solving them, use max flow,” Kelner says. Examples might include airline scheduling, circuit analysis, task distribution in supercomputers, digital image processing, and the assembly of DNA sequences.

Traditionally, Kelner explains, algorithms for calculating max flow would consider one path through a network at a time. If the path had unused capacity, the algorithm would simply send more stuff over it and see what happened.

But Kelner and his colleagues have taken a fundamentally new approach to the problem. They represent a network as a matrix, which is math speak for a big grid of numbers. Each node in the network 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. Since the tools of linear algebra make it possible to simultaneously solve all the equations embodied by all a matrix’s rows, the new algorithm effectively evaluates all the paths through the network at once. For a network like the Internet, with billions of nodes, it could thus solve the max-flow problem hundreds of times faster than its predecessor.

## Uh oh–you've read all of your free articles for this month.

\$179.95/yr US PRICE

• The Evolution of Cambridge

MIT moved to Cambridge in an era of smokestacks and shoe polish. Now it’s exploring ways to energize the high- tech mecca it helped create.

• Speaking of Science

William Barton Rogers enlisted his powers of persuasion to realize the vision that became MIT: a scientific institution dedicated to both theory and practice.

• Making Nanotech Safer

Desirée Plata, PhD ‘09, is on a mission to make nanotube production less toxic and more efficient.

Want more award-winning journalism? Subscribe to Insider Basic.
• Insider Basic {! insider.prices.basic !}*

Six issues of our award winning magazine and daily delivery of The Download, our newsletter of what’s important in technology and innovation.

See details+

What's Included