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. In a paper to be presented at the ACM-SIAM Symposium on Discrete Algorithms in Portland, Ore., Kelner and his colleague Lorenzo Orecchia, an applied mathematics instructor, alongside graduate students Yin Tat Lee and Aaron Sidford, 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. Continue reading this article on Phys.org.
Lee and Sidford help quickly solve “max-flow” problem
January 22, 2014