Communications of the ACM
Researchers Achieve 'Absurdly Fast' Algorithm for Network Flow
For now, it’s primarily a theoretical advance, since the speed improvements kick in only for networks that are far larger than the ones we encounter in the real world, for which maximum flow problems can already be solved fairly quickly (at least, i
Credit: 2Dwork/Shutterstock
A team of computer scientists has come up with a dramatically faster algorithm for one of the oldest problems in computer science: maximum flow. The problem asks how much material can flow through a network from a source to a destination if the links in the network have capacity limits.
The new algorithm is "absurdly fast," said Daniel Spielman of Yale University. "I was actually inclined to believe … algorithms this good for this problem would not exist."
Maximum flow has been studied since the 1950s, when it was formulated to study the Soviet railway system. "It's older than maybe the theory of computer science," said Edith Cohen of Google Research in Mountain View, California. The problem has many applications: internet data flow, airline scheduling and even matching job applicants to open positions. The new paper handles both maximum flow and a more general version of the problem in which you also want to minimize costs. Over the years, these two problems have inspired many of the biggest advances in algorithmic techniques. "They're almost why we have a field of algorithms," Spielman said.
The new algorithm solves these two problems in "almost linear" time, which means that the algorithm's runtime is roughly proportional to the amount of time it takes merely to write down the details of the network in the first place. No other algorithm for these problems comes close to running this fast for all possible networks. The result made him "jump up and down," said Satish Rao of the University of California, Berkeley. "It's amazing."
From Quanta Magazine
View Full Article
No entries found