Metraipolis › archive › dc_ff1601d9cafa

Faster Algorithms for Multimarginal Optimal Transport — arXiv:2608.09513

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.09513
License (as archived)
CC0-1.0
Archived
2026-10-19T09:05:38.494Z
SHA-256 of the archived text
51b23d8d3b86238c4a4576d928950753ce74f3865d439babb7c343ad18a04184
Stable URL of this page
https://metraipolis.com/documento/dc_ff1601d9cafa

How to cite

Faster Algorithms for Multimarginal Optimal Transport — arXiv:2608.09513 — arXiv (en), https://arxiv.org/abs/2608.09513 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ff1601d9cafa (Metraipolis archive dc_ff1601d9cafa, sha256 51b23d8d3b86238c4a4576d928950753ce74f3865d439babb7c343ad18a04184)
BibTeX
@misc{dcff1601d9cafa,
  title = {Faster Algorithms for Multimarginal Optimal Transport — arXiv:2608.09513},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.09513},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ff1601d9cafa; sha256 51b23d8d3b86238c4a4576d928950753ce74f3865d439babb7c343ad18a04184},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.09513. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-11 in math.OC).
Categorie arXiv: Quantum Physics (quant-ph) ; Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2608.09513 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T09:03:32.100Z dalla pagina https://arxiv.org/catchup/math.OC/2026-08-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).