Faster Algorithms for Multimarginal Optimal Transport
Abstract
We study constructive discrete multimarginal optimal transport (MOT) among m distributions on n points, where the cost tensor C has N=nm entries. For additive accuracy ε, let κ=max{1,(max C−min C)/ε}. Classically, we give two algorithms that return exactly feasible additive-ε couplings. A deterministic box--simplex method with rounding runs in O(m2Nκlog N)=Õ(m3Nκ) time, while an exact reduction to positive packing followed by rank-one completion runs in randomized time Õ(m2Nκ). At fixed κ, both match the Ω(N) cost of writing a dense coupling, up to factors in m and logarithms. Quantumly, in the general entry-access model, tensor Sinkhorn followed by sparse recovery returns an exactly feasible additive-ε coupling as a classical list of Õ(m2nκ2) atoms, using Õ(m4√(Nn) κ3) coherent cost queries without materializing the tensor. Finally, for fixed m and constant normalized accuracy, we prove sparse-output lower bounds of Ω̃(N) randomized classical queries, even with unrestricted output size, and Ω̃(√(Nn)) quantum queries for outputs with at most npolylog(n) atoms. Hence, for fixed m and normalized accuracy between (log n)−O(1) and a sufficiently small constant, explicit sparse MOT construction has query complexity Θ̃(N) classically and Θ̃(√(Nn)) quantumly.
Related
- Central limit theorems and bootstrap for sparse regularized multimarginal optimal transport and barycenters
- Sparse Dictionary Learning for Measure-Valued Data via Linearized Optimal Transport: Efficient Algorithms and Sample Complexity
- Path Decompositions of Sparse Graphs via Gaussian Sweeps and Faster Exponential Algorithms
- Parameters Robust Parallelizable Iterative Decoupled Algorithms for Thermo-Poroelasticity with Nonlinear Convective Transport
- Embedding Linear Codes into Optimal Self-Orthogonal Codes Based on Constraint-Preserving Genetic Algorithms
BibTeX
@misc{augustino2026faster,
title = {{Faster Algorithms for Multimarginal Optimal Transport}},
author = {Brandon Augustino and Yue Sun and Atithi Acharya and Shouvanik Chakrabarti and Junhyung Lyle Kim and Shree Hari Sureshbabu and Charlie Che},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.09513},
eprint = {2608.09513},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.09513},
}
RIS
TY - UNPB
TI - Faster Algorithms for Multimarginal Optimal Transport
AU - Brandon Augustino
AU - Yue Sun
AU - Atithi Acharya
AU - Shouvanik Chakrabarti
AU - Junhyung Lyle Kim
AU - Shree Hari Sureshbabu
AU - Charlie Che
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2608.09513
UR - https://arxiv.org/abs/2608.09513
AB - We study constructive discrete multimarginal optimal transport (MOT) among m distributions on n points, where the cost tensor C has N=n^m entries. For additive accuracy ε, let κ=max{1,(max C−min C)/ε}. Classically, we give two algorithms that return exactly feasible additive-ε couplings. A deterministic box--simplex method with rounding runs in O(m^2Nκlog N)=Õ(m^3Nκ) time, while an exact reduction to positive packing followed by rank-one completion runs in randomized time Õ(m^2Nκ). At fixed κ, both match the Ω(N) cost of writing a dense coupling, up to factors in m and logarithms. Quantumly, in the general entry-access model, tensor Sinkhorn followed by sparse recovery returns an exactly feasible additive-ε coupling as a classical list of Õ(m^2nκ^2) atoms, using Õ(m^4√(Nn) κ^3) coherent cost queries without materializing the tensor. Finally, for fixed m and constant normalized accuracy, we prove sparse-output lower bounds of Ω̃(N) randomized classical queries, even with unrestricted output size, and Ω̃(√(Nn)) quantum queries for outputs with at most npolylog(n) atoms. Hence, for fixed m and normalized accuracy between (log n)^−O(1) and a sufficiently small constant, explicit sparse MOT construction has query complexity Θ̃(N) classically and Θ̃(√(Nn)) quantumly.
ER -