# Optimal Transport on Discrete Domains

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jan 2018.

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

- [State Alignment-based Imitation Learning](https://mlsanity.com/paper/1911.10947/) (2019)
- [Recent Advances in Optimal Transport for Machine Learning](https://mlsanity.com/paper/2306.16156/) (2023)
- [Energy-Guided Continuous Entropic Barycenter Estimation for General Costs](https://mlsanity.com/paper/2310.01105/) (2023)
- [Auto-regressive Image Synthesis with Integrated Quantization](https://mlsanity.com/paper/2207.10776/) (2022)
- [Order Constraints in Optimal Transport](https://mlsanity.com/paper/2110.07275/) (2021)
- [Optimal Transport-Assisted Risk-Sensitive Q-Learning](https://mlsanity.com/paper/2406.11774/) (2024)
- [Wassersplines for Neural Vector Field--Controlled Animation](https://mlsanity.com/paper/2201.11940/) (2022)
- [Quantum Theory and Application of Contextual Optimal Transport](https://mlsanity.com/paper/2402.14991/) (2024)
- [Adaptive Pruning for Increased Robustness and Reduced Computational Overhead in Gaussian Process Accelerated Saddle Point Searches](https://mlsanity.com/paper/2510.06030/) (2025)
- [TaskDiff: A Similarity Metric for Task-Oriented Conversations](https://mlsanity.com/paper/2310.15298/) (2023)
- [General Autonomous Cybersecurity Defense: Learning Robust Policies for Dynamic Topologies and Diverse Attackers](https://mlsanity.com/paper/2506.22706/) (2025)
- [FineMoLA: Towards Fine-Grained Motion-Language Alignment from Clip-Level Supervision](https://mlsanity.com/paper/2608.01392/) (2026)
- [Coarse- and fine-scale geometric information content of Multiclass Classification and implied Data-driven Intelligence](https://mlsanity.com/paper/2104.07191/) (2021)
- [Deep Generalized Schr"odinger Bridges: From Image Generation to Solving Mean-Field Games](https://mlsanity.com/paper/2412.20279/) (2024)
- [A Turn Toward Better Alignment: Few-Shot Generative Adaptation with Equivariant Feature Rotation](https://mlsanity.com/paper/2512.21174/) (2025)
- [On the application of the Wasserstein metric to 2D curves classification](https://mlsanity.com/paper/2601.07749/) (2026)

## Abstract (arXiv)

Inspired by the matching of supply to demand in logistical problems, the optimal transport (or Monge--Kantorovich) problem involves the matching of probability distributions defined over a geometric domain such as a surface or manifold. In its most obvious discretization, optimal transport becomes a large-scale linear program, which typically is infeasible to solve efficiently on triangle meshes, graphs, point clouds, and other domains encountered in graphics and machine learning. Recent breakthroughs in numerical optimal transport, however, enable scalability to orders-of-magnitude larger problems, solvable in a fraction of a second. Here, we discuss advances in numerical optimal transport that leverage understanding of both discrete and smooth aspects of the problem. State-of-the-art techniques in discrete optimal transport combine insight from partial differential equations (PDE) with convex analysis to reformulate, discretize, and optimize transportation problems. The end result is a set of theoretically-justified models suitable for domains with thousands or millions of vertices. Since numerical optimal transport is a relatively new discipline, special emphasis is placed on identifying and explaining open problems in need of mathematical insight and additional research.