A team of computer scientists has developed a much faster algorithm for one of the oldest problems in computer science: the maximum flow.
Maximum flow has been researched since the 1950s when it was formulated to study the Soviet railway system. The problem has many applications: data flow on the Internet, flight planning, and even matching applicants to job vacancies. The new paper addresses both maximum data flow and a more general version of the problem where one also wants to minimize costs. Over the years, these two problems have inspired many of the greatest advances in algorithmic techniques.
The new algorithm solves both of these problems in “almost linear” time, meaning that the running time of the algorithm is roughly proportional to the time it takes to write down the details of the network in the first place. No other algorithm for these problems runs anywhere near as fast.