Research map / Learning theory and algorithms / Optimal transport
A Novel Skip Orthogonal List for Dynamic Optimal Transport Problem
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a 2D Skip Orthogonal List data structure that lets the network simplex method maintain the adjusted cost matrix so each pivot takes expected O(|V|) time, enabling fast updates to optimal transport plans under point moves and insertions.
Problem
Efficiently updating the discrete optimal transport plan and cost when point weights or locations change, instead of recomputing from scratch (which needs at least one traversal of all O(|V|^2) edges).
Approach
Extends skip lists to 2D orthogonal lists over the Euler Tour sequence of the basis tree, with lazy range-add and min-query per node, so each network simplex pivot (cut, link, range update, global min) costs expected O(|V|) and only a few simplex iterations are needed after a dynamic change.
Key results
- In dynamic scenarios with |V| up to 40000, the proposed algorithm is about 1000x faster than static Network Simplex (POT) and about 10x faster than Sinkhorn.
- Each simplex pivot (cut, link, range update, global min query) is proved to take expected O(|V|) time, and the 2D skip orthogonal list uses expected O(|V|^2) space with high probability.
- Space complexity of the structure is shown to be O(n^2) with high probability via a probabilistic analysis of level sizes.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the dynamic Network Simplex method with Skip Orthogonal List instead of static Network Simplex | Dynamic optimal transport · Dynamic scenarios at |V|=40000 | running time: about 1000 times faster | Helped |
| Use the dynamic Network Simplex method with Skip Orthogonal List instead of Sinkhorn | Dynamic optimal transport · Dynamic scenarios at |V|=40000 | running time: 10 times faster | Helped |
Limitations
- High memory consumption of the 2D skip orthogonal list structure, which is O(|V|^2) space
- Linked-list structure yields low cache hit rate in practice
- Measured runtime grows slightly faster than linear in practice
Experimental setup
Datasets: MNIST synthetic mixture of two Gaussians in R^784
Benchmarks: MNIST synthetic Gaussian mixture
Metrics: running time
Baselines: Network Simplex Sinkhorn
Builds on: network simplex skip lists Euler Tour Technique orthogonal lists Sinkhorn algorithm
Closest papers by meaning
- A Combinatorial Algorithm for the Semi-Discrete Optimal Transport Problem (NeurIPS 2024 · similarity 0.85)
- Low-Rank Optimal Transport through Factor Relaxation with Latent Coupling (NeurIPS 2024 · similarity 0.84)
- Expected Sliced Transport Plans (ICLR 2025 · similarity 0.83)
- Learning Ultrametric Trees for Optimal Transport Regression (AAAI 2024 · similarity 0.83)
- Stochastic Optimization in Semi-Discrete Optimal Transport: Convergence Analysis and Minimax Rate (NeurIPS 2025 · similarity 0.83)
- Hierarchical Refinement: Optimal Transport to Infinity and Beyond (ICML 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.