# New algorithm can dramatically streamline solutions to the 'max flow' problem

##### Jan 07, 2014 by Helen Knight

Finding the most efficient way to transport items across a network like the U.S. highway system or the Internet is a problem that has taxed mathematicians and computer scientists for decades.

To tackle the problem, researchers have traditionally used a maximum-flow algorithm, also known as "max flow," in which a network is represented as a with a series of nodes, known as vertices, and connecting lines between them, called edges.

Given that each edge has a maximum capacity—just like the roads or the fiber-optic cables used to transmit information around the Internet—such algorithms attempt to find the most efficient way to send goods from one node in the graph to another, without exceeding these constraints.

But as the size of networks like the Internet has grown exponentially, it is often prohibitively time-consuming to solve these problems using traditional computing techniques, according to Jonathan Kelner, an associate professor of applied mathematics at MIT and a member of MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL).

So in a paper to be presented at the ACM-SIAM Symposium on Discrete Algorithms in Portland, Ore., this week, Kelner and his colleague Lorenzo Orecchia, an applied mathematics instructor, alongside graduate students Yin Tat Lee and Aaron Sidford, will describe a new theoretical algorithm that can dramatically reduce the number of operations needed to solve the max-flow problem, making it possible to tackle even huge networks like the Internet or the human genome.

"There has recently been an explosion in the sizes of graphs being studied," Kelner says. "For example, if you wanted to route traffic on the Internet, study all the connections on Facebook, or analyze genomic data, you could easily end up with graphs with millions, billions or even trillions of edges."

Previous max-flow algorithms have come at the problem one edge, or path, at a time, Kelner says. So for example, when sending items from node A to node B, the algorithms would transmit some of the goods down one path, until they reached its maximum capacity, and then begin sending some down the next path.

"Many previous algorithms," Kelner says, "would find a path from point A to point B, send some flow along it, and then say, 'Given what I've already done, can I find another path along which I can send more?' When one needs to send flow simultaneously along many different paths, this leads to an intrinsic limitation on the speed of the algorithm."

But in 2011 Kelner, CSAIL graduate student Aleksander Madry, mathematics undergraduate Paul Christiano, and colleagues at Yale University and the University of Southern California developed a technique to analyze all of the paths simultaneously.

The researchers viewed the graph as a collection of electrical resistors, and then imagined connecting a battery to node A and a ground to node B, and allowing the current to flow through the network. "Electrical current doesn't pick just one path, it will send a little bit of current over every resistor on the network," Kelner says. "So it probes the whole graph globally, studying many paths at the same time."

This allowed the new algorithm to solve the max-flow problem substantially faster than previous attempts.

Now the MIT team has developed a technique to reduce the running time even further, making it possible to analyze even gigantic networks, Kelner says.

Unlike previous algorithms, which have viewed all the paths within a graph as equals, the new technique identifies those routes that create a bottleneck within the network. The team's algorithm divides each graph into clusters of well-connected nodes, and the paths between them that create bottlenecks, Kelner says.

"Our algorithm figures out which parts of the graph can easily route what they need to, and which parts are the bottlenecks. This allows you to focus on the problem areas and the high-level structure, instead of spending a lot of time making unimportant decisions, which means you can use your time a lot more efficiently," he says.

The result is an almost linear , Kelner says, meaning the amount of time it takes to solve a problem is very close to being directly proportional to the number of nodes on the network. So if the number of nodes on the graph is multiplied by 10, the amount of time would be multiplied by something very close to 10, as opposed to being multiplied by 100 or 1,000, he says. "This means that it scales essentially as well as you could hope for with the size of the input," he says.

Shanghua Teng, a professor of computer science at the University of Southern California who was not involved in the latest paper, says it represents a major breakthrough in graph algorithms and optimization software.

"This paper, which is the winner of the best paper award at the [ACM-SIAM] conference, is a result of sustained efforts by Kelner and his colleagues in applying electrical flows to design efficient graph algorithms," Teng says. "The paper contains an amazing array of technical contributions."

## Related Stories

#### New approach to vertex connectivity could maximize networks' bandwidth

Dec 23, 2013

Computer scientists are constantly searching for ways to squeeze ever more bandwidth from communications networks.

#### Short algorithm, long-range consequences

Mar 01, 2013

In the last decade, theoretical computer science has seen remarkable progress on the problem of solving graph Laplacians—the esoteric name for a calculation with hordes of familiar applications in scheduling, image processing, ...

#### Fundamental algorithm gets first improvement in 10 years

Sep 27, 2010

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

#### Machine learning branches out

Nov 14, 2013

Much artificial-intelligence research is concerned with finding statistical correlations between variables: What combinations of visible features indicate the presence of a particular object in a digital ...

#### Explained: Graphs

Dec 17, 2012

When most people hear the word "graph," an image springs to mind: a pair of perpendicular lines overlaid with a line, a curve, or bars of different heights.

#### Enhancing the efficiency of complex computations

Nov 29, 2013

Planning a trip from Berlin to Hamburg, simulating air flows around a new passenger airplane, or friendships on Facebook – many computer applications model relationships between objects by graphs (networks) ...

## Recommended for you

#### UT Dallas professor to develop framework to protect computers' cores

19 hours ago

UT Dallas cybersecurity expert Dr. Zhiqiang Lin has received funding from the U.S. Air Force to develop a defense framework that burrows deep into a computer system to protect its core.

#### Researcher finds hidden efficiencies in computer architecture

23 hours ago

The computer is one of the most complex machines ever devised and most of us only ever interact with its simplest features. For each keystroke and web-click, thousands of instructions must be communicated ...

#### Scientists apply new graph programming method for evolving exascale applications

Apr 18, 2014

(Phys.org) —Hiding the complexities that underpin exascale system operations from application developers is a critical challenge facing teams designing next-generation supercomputers. One way that computer ...

Apr 17, 2014

(Phys.org) —Google engineers working on software to automatically read home and business addresses off photographs taken by Street View vehicles, have created a product so good that not only can it be used ...

#### Preventing AI from developing anti-social and potentially harmful behaviour

Apr 17, 2014

Next time you play a computer at chess, think about the implications if you beat it. It could be a very sore loser!

#### Researcher seeks to lessen failures in computerized visual recognition programs

Apr 17, 2014

Computer programs that use facial or image recognition systems—be it security cameras or applications that search databases for everything from photographs of wanted criminals to images of bears – are like any other technological ...

## More news stories

#### Health care site flagged in Heartbleed review

People with accounts on the enrollment website for President Barack Obama's signature health care law are being told to change their passwords following an administration-wide review of the government's vulnerability to the ...

#### Airbnb rental site raises \$450 mn

Online lodging listings website Airbnb inked a \$450 million funding deal with investors led by TPG, a source close to the matter said Friday.

#### Going nuts? Turkey looks to pistachios to heat new eco-city

Pistachios are already a key ingredient in Turkish baklava, but the country may now have found a new way to exploit the nuts known as "green gold"—by using their shells to heat a new eco-city.

Travelers at Asian airports have asked questions about the March 8 disappearance of Malaysia Airlines Flight 370 while en route from Kuala Lumpur to Beijing. Here are some of them, followed by answers.

#### Under some LED bulbs whites aren't 'whiter than white'

For years, companies have been adding whiteners to laundry detergent, paints, plastics, paper and fabrics to make whites look "whiter than white," but now, with a switch away from incandescent and fluorescent lighting, different ...

#### Free the seed: OSSI nurtures growing plants without patent barriers

(Phys.org) —Members of the Open Source Seed Initiative this week held a rally and seed giveaway event. The group is concerned over restricting access to seeds through patents. They are stirring up public ...

#### Philippines boosts MERS monitoring after UAE nurse scare

The Philippines said Saturday it was stepping up its defences against the deadly MERS virus, with the large numbers of Filipino workers in the Middle East seen as potential carriers.

#### Astronomers discover first self-lensing binary star system

(Phys.org) —A pair of astronomers at the University of Washington has discovered the first known instance of a self-lensing binary-star system. In their paper published in the journal Science, Ethan Kruse ...

#### 'Dressed' laser aimed at clouds may be key to inducing rain, lightning

The adage "Everyone complains about the weather but nobody does anything about it," may one day be obsolete if researchers at the University of Central Florida's College of Optics & Photonics and the University ...

#### Researchers create methylation maps of Neanderthals and Denisovans, compare them to modern humans

(Phys.org) —A team of Israeli, Spanish and German researchers has for the first time created a map of gene expression in Neanderthals and Denisovans and has compared them with modern humans. In their paper ...