# 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: Algorithms are watching

## 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

#### Leaner Fourier transforms: Algorithm separates signals into their individual frequencies using minimal number of samples

13 hours ago

The fast Fourier transform, one of the most important algorithms of the 20th century, revolutionized signal processing. The algorithm allowed computers to quickly perform Fourier transforms—fundamental ...

#### Computational linguists predict TIME's "Person of the Year" using computer model

15 hours ago

On Wednesday 11 December the American TIME Magazine will announce its 'Person of the Year' 2013. An international team of computational linguists has now built a quantitative model that has predicted the ...

#### Hipster, surfer or biker? Computers may soon be able to tell the difference

16 hours ago

(Phys.org) —Are you a hipster, surfer or biker? What is your urban tribe? Your computer may soon be able to tell. Computer scientists at the University of California, San Diego, are developing an algorithm ...

#### Algorithms are watching

Dec 09, 2013

In his prescient novel "1984," English author George Orwell predicted a future that bears an uncanny resemblance to current reality—except for a simple twist. Rather than Big Brother watching, today we ...

#### Explained: Matrices

Dec 06, 2013

Among the most common tools in electrical engineering and computer science are rectangular grids of numbers known as matrices. The numbers in a matrix can represent data, and they can also represent mathematical ...

#### USB sticks may beat Internet hurdles globally

Dec 06, 2013

(Phys.org) —One may think that free software would be of enormous benefit to people in the towns and villages of the globe where the price of proprietary software is restrictively high. Such is not the ...

##### 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.

## More news stories

#### Commercial use of drones has already taken flight

The camera swoops over the green expanse of the Everglades hundreds of feet below, like many helicopter shots you've seen on television. But suddenly it dips and flies through a narrow, shaded canal where kayakers are paddling, ...

#### US risks losing clean electricity if nuclear plants keep closing, report says

Four nuclear power plants, sources of low-emissions electricity, have announced closings this year. If plants continue to shut down instead of extending operations the nation risks losing 60 percent of its clean electricity ...

#### New system allows for high-accuracy, through-wall, 3-D motion tracking (w/ Video)

Imagine playing a video game like Call of Duty or Battlefield and having the ability to lead your virtual army unit while moving freely throughout your house.

#### Valkyrie steps forth as DARPA robotics contender

(Phys.org) —The clock is ticking for robot enthusiasts who are eager to see what happens on the big day, December 20, for the 17 teams competing in the Defense Advanced Research Projects Agency (DARPA) ...

#### NSA: No better way to protect US than surveillance

The NSA chief said Wednesday he knows of no better way his agency can help protect the U.S. from foreign threats than with spy programs that collect billions of phone and Internet records from around the ...

#### A new material for solar panels could make them cheaper, more efficient

A unique solar panel design made with a new ceramic material points the way to potentially providing sustainable power cheaper, more efficiently, and requiring less manufacturing time. It also reaches a four-decade-old ...

#### NASA reveals new results from inside the ozone hole

NASA scientists have revealed the inner workings of the ozone hole that forms annually over Antarctica and found that declining chlorine in the stratosphere has not yet caused a recovery of the ozone hole.

#### The mystery of lizard breath: One-way airflow may be 270 million years old

Air flows mostly in a one-way loop through the lungs of monitor lizards – a breathing method shared by birds, alligators and presumably dinosaurs, according to a new University of Utah study.

#### Team develops temperature-sensitive gelling scaffolds to regenerate craniofacial bone

Rice University bioengineers have developed a hydrogel scaffold for craniofacial bone tissue regeneration that starts as a liquid, solidifies into a gel in the body and liquefies again for removal.

#### Gut bacteria shift quickly after changes in diet, study shows

(HealthDay)—If you were to switch from vegetarianism to meat-eating, or vice-versa, chances are the composition of your gut bacteria would also undergo a big change, a new study suggests.