{"id":"arxiv/2608.09513","url":"https://arxiv.org/abs/2608.09513","tags":["quant-ph","cs.DS","math.OC"],"score":0,"title":"Faster Algorithms for Multimarginal Optimal Transport","domain":"quant-ph","source":"arxiv","authors":["Brandon Augustino","Yue Sun","Atithi Acharya","Shouvanik Chakrabarti","Junhyung Lyle Kim","Shree Hari Sureshbabu","Charlie Che"],"reviews":0,"subject":"quant-ph","summary":"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 $κ=\\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κ\\log N)=\\widetilde O(m^3Nκ)$ time, while an exact reduction to positive packing followed by rank-one completion runs in randomized time $\\widetilde O(m^2Nκ)$. At fixed $κ$, both match the $Ω(N)$…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-08-10","reactions":{}}