Fundamental algorithm gets first improvement in 10 years

Sep 27, 2010 By Larry Hardesty

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. For decades it was a prominent research subject, with new algorithms that solved it more and more efficiently coming out once or twice a year. But as the problem became better understood, the pace of innovation slowed. Now, however, MIT researchers, together with colleagues at Yale and the University of Southern California, have demonstrated the first improvement of the max-flow 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 or the average traffic speeds on congested roads.

More technically, the problem has to do with what mathematicians call graphs. A graph is a collection of vertices and edges, which are generally depicted as circles and the lines connecting them. The standard diagram of a is a graph, as is, say, a family tree. In the max-flow problem, one of the vertices in the graph — one of the circles — is designated the source, where all the stuff comes from; another is designated the drain, where all the stuff is headed. Each of the edges — the lines connecting the circles — has an associated capacity, or how much stuff can pass over it.

Hidden flows

Such graphs model real-world transportation and communication networks in a fairly straightforward way. But their applications are actually much broader, explains Jonathan Kelner, an assistant professor of applied mathematics at MIT, who helped lead the new work. “A very, very large number of optimization problems, if you were to look at the fastest right now for solving them, they use max flow,” Kelner says. Outside of network analysis, a short list of applications that use max flow might include airline scheduling, circuit analysis, task distribution in supercomputers, digital image processing, and DNA sequence alignment.

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.

Graphs to grids

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. This approach turns out to be more efficient than trying out edges one by one.

If N is the number of nodes in a graph, and L is the number of links between them, then the execution of the fastest previous max-flow algorithm was proportional to (N + L)(3/2). The execution of the new algorithm is proportional to (N + L)(4/3). The researchers haven’t in fact written a program that implements their algorithm, and in practice, the performance of an algorithm can depend on factors like how efficiently it’s coded and how well it manages memory. But in theory, for a network like the Internet, which has about 100 billion nodes, the new algorithm could solve the max-flow problem 100 times faster than its predecessor.

The immediate practicality of the algorithm, however, is not what impresses John Hopcroft, the IBM Professor of Engineering and Applied Mathematics at Cornell and a recipient of the Turing Prize, the highest award in . “My guess is that this particular framework is going to be applicable to a wide range of other problems,” Hopcroft says. “It’s a fundamentally new technique. 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.”

This story is republished courtesy of MIT News (web.mit.edu/newsoffice/), a popular site that covers news about MIT research, innovation and teaching.

Explore further: Computer program to take on world's best in Texas Hold 'em

Related Stories

A new kind of counting: Scientists develop computer algorithm to solve previously unsolvable counting problems

Feb 11, 2009

(PhysOrg.com) -- How many different sudokus are there? How many different ways are there to color in the countries on a map? And how do atoms behave in a solid? Researchers at the Max Planck Institute for ...

Solving big problems with new quantum algorithm

Nov 09, 2009

(PhysOrg.com) -- In a recently published paper, Aram Harrow at the University of Bristol and colleagues from MIT in the United States have discovered a quantum algorithm that solves large problems much faster ...

Yale Professor wins Godel Prize for showing how computer algorithms solve problems

Aug 13, 2008

Daniel A. Spielman, professor of applied mathematics and computer science at Yale, has been awarded the prestigious Gödel Prize for developing a technique, known as Smoothed Analysis, that helps predict the ...

P vs. NP -- The most notorious problem in theoretical computer science remains open

Oct 29, 2009

In the 1995 Halloween episode of The Simpsons, Homer Simpson finds a portal to the mysterious Third Dimension behind a bookcase, and desperate to escape his in-laws, he plunges through. He finds himself wander ...

Quantum computing may actually be useful, after all

Oct 09, 2009

(PhysOrg.com) -- In recent years, quantum computers have lost some of their luster. In the 1990s, it seemed that they might be able to solve a class of difficult but common problems — the so-called NP-complete ...

CarTel project researching cars as mobile sensors

Sep 24, 2010

Data about road and traffic conditions can come from radio stations’ helicopters, the Department of Transportation’s roadside sensors, or even, these days, updates from ordinary people with cell phones. ...

Recommended for you

Ears, grips and fists take on mobile phone user ID

24 minutes ago

A research project has been under way to explore a biometric authentication system dubbed Bodyprint, with interesting test results. Bodyprint has been designed to detect users' biometric features using the ...

Russian hackers read Obama emails, report says

11 hours ago

Emails to and from President Barack Obama were read by Russian hackers last year in a breach of the White House's unclassified computer system, The New York Times said Saturday.

Supermarkets welcome cold-comfort edge of F1 aerofoils

16 hours ago

UK-based Williams Advanced Engineering, the technology and engineering services business of the Williams Group, has collaborated with UK-based Aerofoil Energy to develop an aerodynamic device that can reduce ...

Robots and dinosaurs as Japan holds 'Niconico' offline gala

20 hours ago

Robots and dinosaurs mingled with cosplayers as Japan's largest video-sharing website Niconico on Saturday opened its two-day meet-up gala which is expected to attract more than 100,000 fans for the offline ...

Apr 25, 2015

Homes with the accompanying tag of "smart" are often described as deploying devices that can tell the temperature and air quality as signals of the home's health status. What about residents' health status? ...

Starbucks: Computer outage disrupts sales in US, Canada

Apr 25, 2015

A computer outage affecting registers forced Starbucks to give away free drinks Friday before closing stores early.

Arkaleus
not rated yet Sep 27, 2010
Arrrrgh! The machine is becoming self-aware! Flee to the stars!
axemaster
5 / 5 (2) Sep 27, 2010
I'm confused. Why can't you just model this as an electrical network, with the potential going from the origin to the destination? Wouldn't that solve the problem with very little effort?
plasticpower
not rated yet Sep 27, 2010
I'm confused. Why can't you just model this as an electrical network, with the potential going from the origin to the destination? Wouldn't that solve the problem with very little effort?

Agreed. I have been hearing a lot about equations normally found in physics being applied to solve similar problems with great success.
scenage
not rated yet Sep 28, 2010
Hmm, this really doesn't seem new to me. Surprised this only got applied to max flow problems recently? Was doing stuff like this in university in distributive math courses where linear algebra was used.
shavera
not rated yet Sep 28, 2010
@axemaster: how do you account for the different channel capacities? I have a feeling resistances alone would be insufficient.
not rated yet Sep 28, 2010
Good idea.
Perhaps in the electronic circuit you have fixed resistance so there is only one solution. I think here the resistances are all variable as the flow can be change on each vertex/channel up to some max limit.
Perhaps there is an equivalent in electronics where R is a set of unknown resistor values. For that matter plumbing should also work as an analogy.
The LSE in the UK had a plumbing model of the economy. Where water was cash and tanks were components of the economy. The water flowed around the system through pipes regulated by valves.
Applying inter-disciplinary models is a powerful approach to problem solving.