# Computing Kantorovich-Wasserstein Distances on d-dimensional histograms using (d+1)-partite graphs

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 May 2018.

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

- [Normalizing flows as approximations of optimal transport maps via linear-control neural ODEs](https://mlsanity.com/paper/2311.01404/) (2023)
- [The Fourier Discrepancy Function](https://mlsanity.com/paper/2102.02979/) (2021)
- [From Kinetic Theory to AI: a Rediscovery of High-Dimensional Divergences and Their Properties](https://mlsanity.com/paper/2507.11387/) (2025)
- [Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation](https://mlsanity.com/paper/2605.20122/) (2026)
- [GPU-Accelerated Bregman Douglas-Rachford Splitting for Discrete Optimal Transport](https://mlsanity.com/paper/2610.04715/) (2026)

## Abstract (arXiv)

This paper presents a novel method to compute the exact Kantorovich-Wasserstein distance between a pair of d-dimensional histograms having n bins each. We prove that this problem is equivalent to an uncapacitated minimum cost flow problem on a (d+1)-partite graph with (d+1)n nodes and dn^fracd+1d arcs, whenever the cost is separable along the principal d-dimensional directions. We show numerically the benefits of our approach by computing the Kantorovich-Wasserstein distance of order 2 among two sets of instances: gray scale images and d-dimensional biomedical histograms. On these types of instances, our approach is competitive with state-of-the-art optimal transport algorithms.