PRESS-NEWS.org - Press Release Distribution
PRESS RELEASES DISTRIBUTION

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

Research could boost the efficiency even of huge networks like the Internet

2014-01-07
(Press-News.org) Contact information: Abby Abazorius
abbya@mit.edu
617-253-2709
Massachusetts Institute of Technology
New algorithm can dramatically streamline solutions to the 'max flow' problem Research could boost the efficiency even of huge networks like the Internet 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 graph 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 algorithm, 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.

### Written by Helen Knight, MIT News correspondent


ELSE PRESS RELEASES FROM THIS DATE:

When germs attack: A lens into the molecular dance

2014-01-07
When germs attack: A lens into the molecular dance Researchers at Johns Hopkins have zoomed in on what is going on at the molecular level when the body recognizes and defends against an attack of pathogens, and the findings, they say, could influence how drugs are ...

Synthetic genetic clock checks the thermometer

2014-01-07
Synthetic genetic clock checks the thermometer Rice University leads study to counter effects of temperature on synthetic gene circuits HOUSTON – (Jan. 7, 2014) – Genetic systems run like clockwork, attuned to temperature, time of day and many other factors as they regulate ...

Dabrafenib in melanoma: Added benefit not proven

2014-01-07
Dabrafenib in melanoma: Added benefit not proven No differences could be shown for mortality, symptoms and quality of life / concerning side effects, data too uncertain Dabrafenib (trade name: Tafinlar) has been approved in Germany ...

Aflibercept in macular oedema: Added benefit not proven

2014-01-07
Aflibercept in macular oedema: Added benefit not proven Neither the new drug nor the comparator therapy was used in accordance with their approvals in the studies For the third time in one year, the German Institute for Quality ...

Increased risk of prostate cancer in African American men; implications for PSA screening

2014-01-07
Increased risk of prostate cancer in African American men; implications for PSA screening New Rochelle, NY, January 7, 2014—African American men have an increased risk of prostate cancer and are two times more likely than Caucasian American ...

Sugar-burning in the adult human brain is associated with continued growth, and remodeling

2014-01-07
Sugar-burning in the adult human brain is associated with continued growth, and remodeling Research published in the journal Cell Metabolism shows that hotspots of fuel consumption in the adult brain also show key characteristics of developing brain regions SEATTLE, ...

A CNIO research team discovers new regulators of the most prevalent liver disease

2014-01-07
A CNIO research team discovers new regulators of the most prevalent liver disease AP-1 proteins modulate fat accumulation in the liver, a disease termed fatty liver disease (FLD); the pharmacological manipulation of these proteins might help treating ...

Teriflunomide in multiple sclerosis: Added benefit not proven

2014-01-07
Teriflunomide in multiple sclerosis: Added benefit not proven Regarding side effects, there are both positive and negative effects in comparison with beta interferon 1a Teriflunomide (trade name: Aubagio) has been approved in Germany ...

NREL finds a new cellulose digestion mechanism by a fast-eating enzyme

2014-01-07
NREL finds a new cellulose digestion mechanism by a fast-eating enzyme CelA digests cellulose faster than enzymes from commercial preparations Researchers at the Energy Department's National Renewable Energy Laboratory (NREL) have discovered ...

MU researcher's study of African forest elephants helps guide research efforts in the US

2014-01-07
MU researcher's study of African forest elephants helps guide research efforts in the US Study finds that human occupation of an area may not contribute to population decline of an endangered species COLUMBIA, Mo. – Conservation of a protected or endangered ...

LAST 30 PRESS RELEASES:

Pink skies

Monkeys are world’s best yodellers - new research

Key differences between visual- and memory-led Alzheimer’s discovered

% weight loss targets in obesity management – is this the wrong objective?

An app can change how you see yourself at work

NYC speed cameras take six months to change driver behavior, effects vary by neighborhood, new study reveals

New research shows that propaganda is on the rise in China

Even the richest Americans face shorter lifespans than their European counterparts, study finds

Novel genes linked to rare childhood diarrhea

New computer model reveals how Bronze Age Scandinavians could have crossed the sea

Novel point-of-care technology delivers accurate HIV results in minutes

Researchers reveal key brain differences to explain why Ritalin helps improve focus in some more than others

Study finds nearly five-fold increase in hospitalizations for common cause of stroke

Study reveals how alcohol abuse damages cognition

Medicinal cannabis is linked to long-term benefits in health-related quality of life

Microplastics detected in cat placentas and fetuses during early pregnancy

Ancient amphibians as big as alligators died in mass mortality event in Triassic Wyoming

Scientists uncover the first clear evidence of air sacs in the fossilized bones of alvarezsaurian dinosaurs: the "hollow bones" which help modern day birds to fly

Alcohol makes male flies sexy

TB patients globally often incur "catastrophic costs" of up to $11,329 USD, despite many countries offering free treatment, with predominant drivers of cost being hospitalization and loss of income

Study links teen girls’ screen time to sleep disruptions and depression

Scientists unveil starfish-inspired wearable tech for heart monitoring

Footprints reveal prehistoric Scottish lagoons were stomping grounds for giant Jurassic dinosaurs

AI effectively predicts dementia risk in American Indian/Alaska Native elders

First guideline on newborn screening for cystic fibrosis calls for changes in practice to improve outcomes

Existing international law can help secure peace and security in outer space, study shows

Pinning down the process of West Nile virus transmission

UTA-backed research tackles health challenges across ages

In pancreatic cancer, a race against time

Targeting FGFR2 may prevent or delay some KRAS-mutated pancreatic cancers

[Press-News.org] New algorithm can dramatically streamline solutions to the 'max flow' problem
Research could boost the efficiency even of huge networks like the Internet