# Optimal Multimarginal Schr"odinger Bridge: Minimum Spanning Tree over Measure-valued Vertices

arXiv: https://arxiv.org/abs/2509.10626 · HTML: https://mlsanity.com/paper/2509.10626/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 33 references that are in the map.
- First posted on arXiv 12 Sep 2025.

## Builds on (most cited first, 16 of 16)

- [Movie Gen: A Cast of Media Foundation Models](https://mlsanity.com/paper/2410.13720/) (2024)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm](https://mlsanity.com/paper/1802.04367/) (2018)
- [Deep Momentum Multi-Marginal Schr"odinger Bridge](https://mlsanity.com/paper/2303.01751/) (2023)
- [Multi-marginal optimal transport: theory and applications](https://mlsanity.com/paper/1406.0026/) (2014)
- [An Optimal Transport approach for the Schr"odinger bridge problem and convergence of Sinkhorn algorithm](https://mlsanity.com/paper/1911.06850/) (2019)
- [On the Complexity of Approximating Multimarginal Optimal Transport](https://mlsanity.com/paper/1910.00152/) (2019)
- [Multi-marginal Schr"odinger Bridges with Iterative Reference Refinement](https://mlsanity.com/paper/2408.06277/) (2024)
- [Tree-Based Diffusion Schr"odinger Bridge with Applications to Wasserstein Barycenters](https://mlsanity.com/paper/2305.16557/) (2023)
- [Polynomial-time algorithms for Multimarginal Optimal Transport problems with structure](https://mlsanity.com/paper/2008.03006/) (2020)
- [On the complexity of the optimal transport problem with graph-structured cost](https://mlsanity.com/paper/2110.00627/) (2021)
- [Multi-marginal optimal transport and probabilistic graphical models](https://mlsanity.com/paper/2006.14113/) (2020)
- [Multi-marginal Schrodinger bridges](https://mlsanity.com/paper/1902.08319/) (2019)
- [Oh SnapMMD! Forecasting Stochastic Dynamics Beyond the Schr"odinger Bridge's End](https://mlsanity.com/paper/2505.16082/) (2025)
- [Path Structured Multimarginal Schr"odinger Bridge for Probabilistic Learning of Hardware Resource Usage by Control Software](https://mlsanity.com/paper/2310.00604/) (2023)
- [Stochastic Learning of Computational Resource Usage as Graph Structured Multimarginal Schr"odinger Bridge](https://mlsanity.com/paper/2405.12463/) (2024)

## Built on by (most cited first, 1 of 1)

- [Generative Profiling for Soft Real-Time Systems and its Applications to Resource Allocation](https://mlsanity.com/paper/2604.01441/) (2026)

## Abstract (arXiv)

The Multimarginal Schr"odinger Bridge (MSB) finds the optimal coupling among a collection of random vectors with known statistics and a known correlation structure. In the MSB formulation, this correlation structure is specified a priori as an undirected connected graph with measure-valued vertices. In this work, we formulate and solve the problem of finding the optimal MSB in the sense we seek the optimal coupling over all possible graph structures. We find that computing the optimal MSB amounts to solving the minimum spanning tree problem over measure-valued vertices. We show that the resulting problem can be solved in two steps. The first step constructs a complete graph with edge weight equal to a sum of the optimal value of the corresponding bimarginal SB and the entropies of the endpoints. The second step solves a standard minimum spanning tree problem over that complete weighted graph. Numerical experiments illustrate the proposed solution.