# Efficient and Exact Multimarginal Optimal Transport with Pairwise Costs

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Aug 2022.

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

- [Longitudinal Flow Matching for Trajectory Modeling](https://mlsanity.com/paper/2510.03569/) (2025)
- [Sobolev Gradient Ascent for Optimal Transport: Barycenter Optimization and Convergence Analysis](https://mlsanity.com/paper/2505.13660/) (2025)
- [Neural Estimation for Scaling Entropic Multimarginal Optimal Transport](https://mlsanity.com/paper/2506.00573/) (2025)
- [Learning In-between Imagery Dynamics via Physical Latent Spaces](https://mlsanity.com/paper/2310.09495/) (2023)

## Abstract (arXiv)

In this paper, we address the numerical solution to the multimarginal optimal transport (MMOT) with pairwise costs. MMOT, as a natural extension from the classical two-marginal optimal transport, has many important applications including image processing, density functional theory and machine learning, but yet lacks efficient and exact numerical methods. The popular entropy-regularized method may suffer numerical instability and blurring issues. Inspired by the back-and-forth method introduced by Jacobs and L'eger, we investigate MMOT problems with pairwise costs. First, such problems have a graphical representation and we prove equivalent MMOT problems that have a tree representation. Second, we introduce a noval algorithm to solve MMOT on a rooted tree, by gradient based method on the dual formulation. Last, we obtain accurate solutions which can be used for the regularization-free applications.