# Theory and Approximate Solvers for Branched Optimal Transport with Multiple Sources

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

## Key facts

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

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Optimal Transport for Domain Adaptation](https://mlsanity.com/paper/1507.00504/) (2015)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [The Fermat-Torricelli Problem and Weiszfeld's Algorithm in the Light of Convex Analysis](https://mlsanity.com/paper/1302.5244/) (2013)

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

- [Branched Schr"odinger Bridge Matching](https://mlsanity.com/paper/2506.09007/) (2025)
- [Y-Shaped Generative Flows](https://mlsanity.com/paper/2510.11955/) (2025)
- [Heuristic Optimal Transport in Branching Networks](https://mlsanity.com/paper/2311.06650/) (2023)
- [The Central Spanning Tree Problem](https://mlsanity.com/paper/2404.06447/) (2024)

## Abstract (arXiv)

Branched Optimal Transport (BOT) is a generalization of optimal transport in which transportation costs along an edge are subadditive. This subadditivity models an increase in transport efficiency when shipping mass along the same route, favoring branched transportation networks. We here study the NP-hard optimization of BOT networks connecting a finite number of sources and sinks in ℝ2. First, we show how to efficiently find the best geometry of a BOT network for many sources and sinks, given a topology. Second, we argue that a topology with more than three edges meeting at a branching point is never optimal. Third, we show that the results obtained for the Euclidean plane generalize directly to optimal transportation networks on two-dimensional Riemannian manifolds. Finally, we present a simple but effective approximate BOT solver combining geometric optimization with a combinatorial optimization of the network topology.