Skip to Content
MIT News magazine

Maximum Plus

Classic logistics algorithm gets a makeover
December 21, 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 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.

Keep Reading

Most Popular

Workers disinfect the street outside Shijiazhuang Railway Station
Workers disinfect the street outside Shijiazhuang Railway Station

Why China is still obsessed with disinfecting everything

Most public health bodies dealing with covid have long since moved on from the idea of surface transmission. China’s didn’t—and that helps it control the narrative about the disease’s origins and danger.

individual aging affects covid outcomes concept
individual aging affects covid outcomes concept

Anti-aging drugs are being tested as a way to treat covid

Drugs that rejuvenate our immune systems and make us biologically younger could help protect us from the disease’s worst effects.

Europe's AI Act concept
Europe's AI Act concept

A quick guide to the most important AI law you’ve never heard of

The European Union is planning new legislation aimed at curbing the worst harms associated with artificial intelligence.

Stay connected

Illustration by Rose WongIllustration by Rose Wong

Get the latest updates from
MIT Technology Review

Discover special offers, top stories, upcoming events, and more.

Thank you for submitting your email!

Explore more newsletters

It looks like something went wrong.

We’re having trouble saving your preferences. Try refreshing this page and updating them one more time. If you continue to get this message, reach out to us at customer-service@technologyreview.com with a list of newsletters you’d like to receive.