# On the complexity of the optimal transport problem with graph-structured cost

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

## Key facts

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

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [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)
- [On the relation between optimal transport and Schr"odinger bridges: A stochastic control viewpoint](https://mlsanity.com/paper/1412.4430/) (2014)
- [An Optimal Transport approach for the Schr"odinger bridge problem and convergence of Sinkhorn algorithm](https://mlsanity.com/paper/1911.06850/) (2019)
- [Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm](https://mlsanity.com/paper/2002.04783/) (2020)
- [On the Complexity of Approximating Multimarginal Optimal Transport](https://mlsanity.com/paper/1910.00152/) (2019)
- [Polynomial-time algorithms for Multimarginal Optimal Transport problems with structure](https://mlsanity.com/paper/2008.03006/) (2020)
- [Multi-marginal optimal transport and probabilistic graphical models](https://mlsanity.com/paper/2006.14113/) (2020)
- [Inference with Aggregate Data: An Optimal Transport Approach](https://mlsanity.com/paper/2003.13933/) (2020)
- [Scalable computation of dynamic flow problems via multi-marginal graph-structured optimal transport](https://mlsanity.com/paper/2106.14485/) (2021)
- [Statistical learning in Wasserstein space](https://mlsanity.com/paper/2004.07875/) (2020)

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

- [Hierarchical Multi-Marginal Optimal Transport for Network Alignment](https://mlsanity.com/paper/2310.04470/) (2023)
- [Scalable Unbalanced Sobolev Transport for Measures on a Graph](https://mlsanity.com/paper/2302.12498/) (2023)
- [Generalized Sobolev Transport for Probability Measures on a Graph](https://mlsanity.com/paper/2402.04516/) (2024)
- [Optimal Transport for Measures with Noisy Tree Metric](https://mlsanity.com/paper/2310.13653/) (2023)
- [Tree-Sliced Wasserstein Distance: A Geometric Perspective](https://mlsanity.com/paper/2406.13725/) (2024)
- [The Synergy Between Optimal Transport Theory and Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2401.10949/) (2024)
- [Distance-Based Tree-Sliced Wasserstein Distance](https://mlsanity.com/paper/2503.11050/) (2025)
- [Optimal Transport for Fairness: Archival Data Repair using Small Research Data Sets](https://mlsanity.com/paper/2403.13864/) (2024)
- [Stochastic Learning of Computational Resource Usage as Graph Structured Multimarginal Schr"odinger Bridge](https://mlsanity.com/paper/2405.12463/) (2024)
- [Tree-Sliced Wasserstein Distance with Nonlinear Projection](https://mlsanity.com/paper/2505.00968/) (2025)
- [Sobolev Gradient Ascent for Optimal Transport: Barycenter Optimization and Convergence Analysis](https://mlsanity.com/paper/2505.13660/) (2025)
- [Fast computation of the TGOSPA metric for multiple target tracking via unbalanced optimal transport](https://mlsanity.com/paper/2503.09449/) (2025)
- [Optimal Multimarginal Schr"odinger Bridge: Minimum Spanning Tree over Measure-valued Vertices](https://mlsanity.com/paper/2509.10626/) (2025)
- [Beckman Defense](https://mlsanity.com/paper/2301.01495/) (2023)

## Abstract (arXiv)

Multi-marginal optimal transport (MOT) is a generalization of optimal transport to multiple marginals. Optimal transport has evolved into an important tool in many machine learning applications, and its multi-marginal extension opens up for addressing new challenges in the field of machine learning. However, the usage of MOT has been largely impeded by its computational complexity which scales exponentially in the number of marginals. Fortunately, in many applications, such as barycenter or interpolation problems, the cost function adheres to structures, which has recently been exploited for developing efficient computational methods. In this work we derive computational bounds for these methods. With m marginal distributions supported on n points, we provide a  tilde O(d(G)m n2ε-2) bound for a ε-accuracy when the problem is associated with a tree with diameter d(G). For the special case of the Wasserstein barycenter problem, which corresponds to a star-shaped tree, our bound is in alignment with the existing complexity bound for it.