Beating the Worst-Case $O(n^2)$ Per-Iteration Update Time: A Novel Dynamic Network Simplex Method for Optimal Transport

Optimal Transport is widely applied in fields such as computer vision, machine learning, and operations research. It seeks a minimum-cost transport plan from source to target domain under supply and demand constraints. However, optimal transport problems in dynamic scenarios face the challenge of high complexity in real-time adjustments to transport plans. To overcome this computational barrier, we aim to develop an efficient dynamic algorithm for the seminal Network Simplex method. We find the primary difficulty lies in the rapid and effective maintenance of the reduced cost matrix, with up to $n^2$ entries (”$n$” is the number of input points). To address this, we propose a novel “Bi-resolution Matrix Decomposition Tree” technique for maintaining matrix operations. By indexing the reduced cost matrix with Euler tour sequences and maintaining a hierarchical bi-resolution block decomposition, it reduces the worst-case time per simplex iteration to $O(n)$. Finally, we demonstrate our method's effectiveness through experiments on synthetic and real-world datasets.