The fastest network flow algorithm to date, netizens: almost as fast as the mathematical theory

Qubits
2024/06/30 14:04

fastest and near-perfect Network Flow algorithm so far, here!

How fast?

For any type of network, the computation speed is almost as fast as the mathematical theory.

And it is the kind that calculates the maximum traffic at the lowest cost.

This is the latest research from the team of Rasmus Kyng from the Department of Computer Science at ETH Zurich:

In fact, as early as two years ago, the "previous generation" research done by Jingye's team has become popular in the circle, and it has been rated as one of the top ten discoveries in computer science by Quanta Magazine.

Daniel A. Spielman, a pioneer of network streaming algorithms, also gave a fairly high rating:

It's ridiculously fast, like a Porsche supercar.

And just recently, they brought an "evolutionary" version of their research to the ACM Symposium on Computational Theory (STOC) –

No matter what paths are added or removed from the network, they can still be calculated at an almost linear speed with the "posture" of the lowest cost and the maximum amount of traffic.

It's like hiking, no matter if the road gets steeper or steeper, I keep going at a high speed and get to the finish line.

ETH Zurich's official assessment is:

Ultrafast algorithms lay the foundation for the efficient calculation of ultra-large dynamically changing networks in the future, which is expected to change the entire research field.

So how did Jingye's team do this?

Network flow is a theory and method in graph theory that studies a class of optimization problems on the network.

This question was raised as early as 1955 by T.E. Harris in his study of the maximum throughput of railways in order to find the maximum amount of transportation between two points.

In 1956, L.R. Ford and D.R. Fulkerson and others proposed an algorithm to solve this kind of problem, thus establishing the network flow theory.

Moreover, the network flow algorithm has great application value in solving practical problems.

For example, if you're using the European transport network and want to find the fastest and cheapest route to get as much cargo as possible from Copenhagen to Milan, this is where the network flow algorithm comes into play.

For this problem, it used to take much longer to calculate the optimal traffic than it did to process the network data.

And as networks become larger and more complex, the computational time required grows much faster than the actual size of the computational problem.

That's why we can also see that computers sometimes can't calculate the traffic in the network.

But the algorithm proposed by Jingye's team broke this situation in one fell swoop-

Not only is the "extra" computation time required to read network data to the solution negligible, but even if you redesign a route or add a new route, it is negligible.

In principle, all computational methods face the challenge of having to analyze the network multiple iterations in order to find the best traffic and the least-cost route.

Before Jingye's team, researchers tended to choose between two key strategies:

The approach of the Jingye team is that adults do not do multiple-choice questions, and the advantages of both are required, and a new method is created by combination:

Our approach is based on a number of small, efficient, and low-cost computational steps that add up to be much faster than several large computational steps.

This played a key role in the development of an almost linear time algorithm.

In this latest study, we propose a series of almost linear time algorithms for incremental graphs.

(An incremental graph is a directed graph that changes dynamically over time, mainly by inserting edges.) ）

The algorithm proposed in this paper mainly solves the following problems:

The main technical contribution of the paper is to propose a deterministic data structure capable of returning an approximate minimum ratio loop in an amortized almost linear time for each update in a fully dynamic graph.

Combined with the framework of the Brand-Liu-Sidford (STOC 2023) interior point method, this paper presents the first algorithm to determine the minimum cost flow in the delta graph to reach a given threshold.

In addition to this, the team used and designed new mathematical tools to further speed up their algorithms.

The results show that the algorithms in this paper theoretically provide an effective solution to the incremental graph problem, and these algorithms are significantly better than the previous algorithms in terms of time complexity.

However, the foundation laid by the Jingye team to solve very large-scale problems that were previously inefficient is only one of the effects of these significantly faster network flow algorithms.

On a deeper level, they have also changed the way computers calculate complex tasks.

As an international team of researchers at the University of California, Berkeley, commented:

In the last decade, there has been a revolution in theoretical foundations in the fundamental problems of theoretical computer science, in order to obtain provably fast algorithms.

The study was conducted by three authors from ETH Zurich.

Rasmus Kyng is an assistant professor in the Department of Computer Science at ETH Zurich, where his research focuses on fast algorithms for graph problems and convex optimization, probability and difference theory, fine-grained complexity theory, and applications in machine learning.

△Rasmus Kyng

Another key contributor to the research is Dr. Maximilian Probst, a senior associate in the Jingye group, focusing on graph algorithms, optimization, and data structures.

△Maximilian Probst

In addition, there are two Chinese authors in this study: Li Chen from CMU and Yang P. Liu from Princeton.

If you are interested in this research, please click the link below to learn more.

This article is from Xinzhi self-media and does not represent the views and positions of Business Xinzhi.If there is any suspicion of infringement, please contact the administrator of the Business News Platform.Contact: system@shangyexinzhi.com