Research map / Learning theory and algorithms / Optimal transport
A Combinatorial Algorithm for the Semi-Discrete 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 combinatorial primal-dual cost-scaling algorithm for semi-discrete 2-Wasserstein optimal transport that runs in O(n^4 log n log(1/ε)) time, plus an O(N)-size data structure for fast discrete OT queries against a large fixed distribution.
Problem
Computing an ε-close optimal transport plan between a continuous distribution µ (accessible via a triangle-mass oracle) and a discrete distribution ν in R^d; existing exact/approximate methods are slow, exponential in d and log(1/ε), or assume smoothness of µ.
Approach
Extends the combinatorial primal-dual framework of discrete OT (augmenting paths on a residual graph with dual weights on support points only) to continuous space by using a residual graph over the arrangement of δ-expanded Voronoi cells, with admissibility defined on consecutive edge pairs and a DFS-based search/weight-increase/acyclify cycle within a cost-scaling loop.
Key results
- Computes an ε-close semi-discrete W2-OT plan in R^2 in O(n^3(Φ+n log n) log(Δ/ε)) time, i.e., O(n^4 log n log(1/ε)) with Φ=O(n), improving on O(n^9 log(Δ/ε)) of prior cost-scaling work.
- Data structure with O(N) space answers discrete OT queries with support k in O(k^3 sqrt(N) log(1/ε)) time in 2D.
- Exact discrete OT plans for integer-coordinate inputs with rational masses for even p in O(k^3(sqrt(N)+k log k) log(λT)) time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the combinatorial primal-dual framework with an O(n3)-edge residual graph instead of constructing a discrete OT instance with O(n5) edges | Semi-discrete W2 OT algorithm · Semi-discrete W2 OT (R2) | worst-case runtime: O(n9 log ∆/ε) -> O(n3(Φ + n log n) log ∆/ε) | Helped |
| preprocess the large discrete distribution with a simplex range-searching data structure | Combinatorial algorithm · Discrete OT query (R2) | query time: O(k3(√N + k log k) log ∆/ε) | Helped |
Limitations
- Mass-of-triangle oracle Φ assumed O(1) in the main bound; runtime depends on it
- Results are for 2D; higher-dimensional extension has runtime O(n^{d+1}) and no poly(n,d,1/ε) algorithm
- Only theoretical; no empirical evaluation reported
Experimental setup
Metrics: worst-case running time additive approximation error
Baselines: Agarwal et al. cost-scaling algorithm (O(n^9 log(Δ/ε))) Oliker-Prussner numerical algorithm
Builds on: Orlin discrete OT algorithm Agarwal et al. cost-scaling semi-discrete OT Oliker-Prussner numerical algorithm
Closest papers by meaning
- Stochastic Optimization in Semi-Discrete Optimal Transport: Convergence Analysis and Minimax Rate (NeurIPS 2025 · similarity 0.88)
- Uncovering Challenges of Solving the Continuous Gromov-Wasserstein Problem (NeurIPS 2026 · similarity 0.88)
- A Provably Convergent and Practical Algorithm for Gromov–Wasserstein Optimal Transport (NeurIPS 2026 · similarity 0.88)
- Generalized Sobolev Transport for Probability Measures on a Graph (ICML 2024 · similarity 0.88)
- Semidefinite Relaxations of the Gromov-Wasserstein Distance (NeurIPS 2024 · similarity 0.87)
- Computing Optimal Transport Maps and Wasserstein Barycenters Using Conditional Normalizing Flows (ICML 2025 · similarity 0.87)
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.