Skip to content

Faster Algorithms for Multimarginal Optimal Transport

Aug 2026 · arXiv.org · Vol abs/2608.09513 · 0 citations · 44 references
Physics Computer Science Mathematics

TL;DR

For fixed $m$ and constant normalized accuracy, this work proves sparse-output lower bounds of $\widetilde\Omega(N)$ randomized classical queries, even with unrestricted output size, and $\widetilde\Omega(\sqrt{Nn})$ quantum queries for outputs with at most $n\operatorname{polylog}(n)$ atoms.

Abstract

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 $\varepsilon$, let $\kappa=\max\{1,(\max C-\min C)/\varepsilon\}$. Classically, we give two algorithms that return exactly feasible additive-$\varepsilon$ couplings. A deterministic box--simplex method with rounding runs in $O(m^2N\kappa\log N)=\widetilde O(m^3N\kappa)$ time, while an exact reduction to positive packing followed by rank-one completion runs in randomized time $\widetilde O(m^2N\kappa)$. At fixed $\kappa$, both match the $\Omega(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-$\varepsilon$ coupling as a classical list of $\widetilde O(m^2n\kappa^2)$ atoms, using $\widetilde O(m^4\sqrt{Nn}\,\kappa^3)$ coherent cost queries without materializing the tensor. Finally, for fixed $m$ and constant normalized accuracy, we prove sparse-output lower bounds of $\widetilde\Omega(N)$ randomized classical queries, even with unrestricted output size, and $\widetilde\Omega(\sqrt{Nn})$ quantum queries for outputs with at most $n\operatorname{polylog}(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 $\widetilde\Theta(N)$ classically and $\widetilde\Theta(\sqrt{Nn})$ quantumly.

View source

Similar papers

Sep 2026

Improved Algorithms for Beck-Fiala with Bounded Sets

We give an efficient algorithm with improved algorithmic guarantees for the (offline) Beck--Fiala problem when the sets have bounded size. Let $A$ be an arbitrary matrix $A\in\{0,1\}^{m\times n}$ with at most $d$ ones per column and at most $s$ ones per row. Let $\log^*$ denote the iterated logarithm and $\ell_j$ denot...

Dylan J. Altschuler · 1 citation
Sep 2026

Vector Balancing in Polynomial Time

The Koml\'os problem asks for signs $\varepsilon\in\{-1,1\}^n$ with $\|A\varepsilon\|_\infty$ bounded by an absolute constant whenever the columns of $A\in\mathbb R^{m\times n}$ have Euclidean norm at most $1$. We give the first polynomial-time algorithm for this problem in the unit-cost real-RAM model. Our determinist...

Sheng Guo, Ethan X. Fang, Jun-Wei Lu · 4 citations · ⚡2
Preprint Oct 2026

Stable and Online Algorithms for Random Matrix Discrepancy

We study the average-case matrix discrepancy problem: given independent normalized $d\times d$ Gaussian orthogonal ensemble matrices $A_1,\dots,A_N$ and a fixed margin $\kappa>0$, find signs $\sigma_1,\dots,\sigma_N\in\{-1,1\}$ such that the operator norm of $\sum_{i=1}^N \sigma_i A_i$ is at most $\kappa\sqrt{N}$. Focu...

Eren C. Kızıldağ, Shuang-Ping Li · 2 citations
Preprint Oct 2026

Lattices with Large Kissing Number from Local Density

Let $\kappa_p(n)$ denote the maximum kissing number of a lattice $\mathcal{L} \subset \mathbb{R}^n$. We prove that $\kappa_p(n) \geq 2^{\Omega(\sqrt{n})}$ for all $p\ge 1$ and that $\kappa_p(n) \geq \Omega(\alpha_p^n)$ for all $p>2$, where $\alpha_p>1$ is a constant depending only on $p$. In particular, our former resu...

Huck Bennett, Minki Hhan, Zi-Han Li et al. · 0 citations
Sep 2026

Sampling Matchings in Near-linear Time

For every fixed activity $\lambda>0$, we establish three results for the monomer--dimer model on an $n$-vertex simple graph $G$ with $m\ge1$ edges and maximum degree $\Delta$. 1. Near-linear mixing and sampling. Single-edge Glauber dynamics has mixing time $O_\lambda(m[\log^2 n+\log(1/\varepsilon)])$, giving a near-lin...

Tian-Shun Miao, Yi-Tong Yin · 1 citation
Sep 2026

Intrinsic-Dimensional Wasserstein Guarantees for Private Synthetic Measures

We study an $\varepsilon$-differentially private synthetic measure for $n$ points in $[0,1]^d$ by applying the existing PrivTree algorithm to construct an adaptive binary partition and then privately releasing its leaf masses. We consider the worst-case data model without any sampling or population-distribution assumpt...

Yi-Yun He · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.