🤖 AI

A Novel Skip Orthogonal List for Dynamic Optimal Transport Problem

This paper proposes a novel algorithm utilizing a 2D Skip Orthogonal List and dynamic tree techniques to efficiently update optimal transport plans in dynamic scenarios by leveraging the simplex method, significantly outperforming existing approaches that require full recomputation.

Original authors: Xiaoyang Xu, Hu Ding

Published 2026-07-31

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: Xiaoyang Xu, Hu Ding

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a logistics manager for a massive delivery company. Your job is to move packages from a warehouse full of items (the "supply") to a city full of customers (the "demand"). You want to do this in the cheapest way possible, considering the distance and the weight of every single package. This is a classic puzzle in mathematics called Optimal Transport. It's like solving a giant, three-dimensional jigsaw where every piece has a price tag, and you need to find the arrangement that costs the least.

For a long time, mathematicians and computer scientists have had great tools to solve this puzzle when the world is static—when the warehouse and the city stay exactly the same. But in the real world, things change. A new customer moves in, a package gets heavier, or a road gets blocked. If you have to re-solve the entire puzzle from scratch every time a single thing changes, it's like tearing down a whole skyscraper just to fix a leaky faucet. It takes too long and wastes too much energy. The big question is: Can we fix the plan quickly, just by adjusting the parts that changed, without redoing the whole thing?

This is exactly what the researchers in this paper tackled. They looked at a "dynamic" version of the problem, where data points (like delivery locations or weights) shift around. They realized that while some old methods could handle these changes, they were still too slow, essentially forcing the computer to re-check every single road in the network every time a tiny change happened.

To solve this, the authors invented a brand-new way to organize information called a Skip Orthogonal List. Think of a standard list of tasks like a long line of people waiting for a bus. If you need to find the person at the very back, you have to walk past everyone. A "Skip List" is like a magical elevator system built into that line; it has extra shortcuts that let you jump over huge chunks of the line to get to the person you need much faster. The authors took this idea and made it two-dimensional, creating a grid of shortcuts.

They combined this grid with a technique called an "Euler Tour," which is a clever way of turning a complex tree-like map of connections into a single, continuous loop. By layering these shortcuts onto the loop, they created a structure that can instantly spot the best place to make a change and update the plan in a flash.

The paper shows that when you use this new structure, the computer doesn't need to scan the whole network anymore. Instead of checking every single road (which gets slower and slower as the network grows), the new method only checks the few roads that actually need attention. In their experiments, when they tested this on datasets with up to 40,000 points, their method was about 1,000 times faster than the standard "Network Simplex" algorithm and 10 times faster than the popular "Sinkhorn" algorithm.

The researchers found that this speed boost works best when the changes are small and local—like moving one delivery truck or adjusting one weight—which is exactly how real-world data usually behaves. While the method does require a bit more memory to store all these magical shortcuts, the trade-off is worth it for the massive speed gains. Essentially, they built a "smart update button" for complex logistics problems, proving that you don't always need to start over to get a better answer; sometimes, you just need the right map to find the quickest fix.

Technical Summary: A Novel Skip Orthogonal List for Dynamic Optimal Transport Problem

Problem Statement
The paper addresses the Dynamic Optimal Transport (OT) problem. While the discrete OT problem—finding a transport plan minimizing the cost of moving mass between two datasets—is well-studied in static settings, real-world applications often involve dynamic changes. These include modifications to data point weights, spatial positions, or the addition/deletion of points. Existing static algorithms, such as the Sinkhorn algorithm and the Network Simplex algorithm, are inefficient in these scenarios. Upon any modification, they typically require re-computing the solution by traversing the entire network or regularizing the whole solution matrix, resulting in a time complexity of $\Omega(|V|^2)$ , where $|V|$ is the number of supply and demand nodes. The authors pose the question: Can we efficiently update the optimal transport plan when weights or locations change, rather than re-computing from scratch?

Methodology
The proposed solution integrates the Simplex method with a novel data structure called the Skip Orthogonal List. The approach relies on two main strategies:

Reduction to Simplex Iterations:
The authors observe that dynamic modifications in OT typically induce only local changes to the optimal solution. Instead of a full re-computation, the problem is reduced to a small number of simplex iterations (specifically, pivoting operations).
- Spatial Position Modifications and Weight Modifications are handled by performing primal or dual simplex iterations, respectively, starting from the previous optimal solution.
- Point Insertion/Deletion is managed by maintaining a pool of zero-weight nodes, allowing the basis to be updated with minimal structural changes.
- The authors assume that the number of required simplex iterations, denoted as $s$ , is significantly smaller than the total number of nodes ( $s \ll |V|$ ).
Skip Orthogonal List Data Structure:
To accelerate each simplex iteration, the authors introduce the Skip Orthogonal List, a 2D extension of the Skip List combined with the Euler Tour Technique.
- Structure: It maintains a cyclic ordered set representing the edges of the spanning tree in the network flow formulation. The structure is a hierarchical collection of 2D circular orthogonal lists, where each layer contains a subset of elements from the layer below, determined by geometrically distributed random heights.
- Operations: The data structure supports:
  - Cut/Link: Splitting or merging trees (forest operations) by cutting or linking rows and columns in the 2D list.
  - Range Update: Efficiently updating the adjusted cost matrix ( $C^\pi$ ) across specific regions (e.g., $V_1 \times V_2$ ) using lazy propagation tags.
  - Global Minimum Query: Finding the variable with the smallest adjusted cost to pivot in, which is critical for the simplex step.
- Complexity: By leveraging the skipping technique and lazy propagation, the authors achieve an expected $O(|V|)$ time complexity for each simplex iteration (including pivot selection and cost matrix updates), compared to the $O(|V|^2)$ complexity of brute-force approaches.

Key Contributions

Novel Data Structure: The introduction of the Skip Orthogonal List, which adapts skip lists to maintain 2D Euler Tour sequences. This structure supports cyclic ordered set maintenance and range queries/updates in expected linear time relative to the number of nodes.
Dynamic Algorithm: A dynamic network simplex algorithm that reduces the OT update problem to a sequence of simplex iterations, where each iteration is accelerated by the new data structure.
Theoretical Guarantees: The paper proves that the space complexity is $O(|V|^2)$ with high probability and that the expected time complexity for each simplex iteration is $O(|V|)$ . Consequently, the total time complexity for handling evolving datasets is $O(s|V|)$ , where $s$ is the number of iterations.

Experimental Results
The authors evaluated their algorithm against the static Network Simplex and Sinkhorn algorithms using both synthetic Gaussian datasets and the real-world MNIST dataset.

Performance: In dynamic scenarios (spatial position modification and point insertion), the proposed algorithm demonstrated significant speedups. For datasets with $|V| = 40,000$ , the dynamic algorithm was approximately 1,000 times faster than the static Network Simplex and 10 times faster than the Sinkhorn algorithm.
Scalability: The performance advantage grew as the number of nodes increased. The running time showed a slightly higher-than-linear trend, attributed to practical factors like cache hit rates and the number of simplex iterations required, though the theoretical expectation remains linear per iteration.
Stability: Operations involving point insertion and deletion (which strictly require linear time) were more stable and faster than weight or spatial modifications, which depend on the number of simplex iterations needed to restore optimality.

Significance and Claims
The paper claims that its primary contribution is enabling efficient dynamic updates for optimal transport problems, a capability previously limited by the high cost of re-computation in existing methods.

Motivation: The work is motivated by applications in dataset similarity, time series analysis, and neuroimage analysis, where data evolves over time, and iterative refinement is preferable to full re-computation.
Modesty: The authors acknowledge limitations, noting that the $O(|V|^2)$ space complexity is relatively high and that the linked-list nature of the structure may result in lower cache hit rates compared to array-based structures. They suggest that future work could focus on developing memory-friendly alternatives with similar complexity.
Conclusion: The paper asserts that for dynamic scenarios where changes are local and small, the proposed method significantly outperforms existing static algorithms, making it a practical tool for real-time or iterative optimal transport applications.

Technical Summary: A Novel Skip Orthogonal List for Dynamic Optimal Transport Problem

More like this