# Solving a Special Type of Optimal Transport Problem by a Modified Hungarian Algorithm

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 49 references that are in the map.
- First posted on arXiv 29 Oct 2022.

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [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)
- [Wasserstein Dependency Measure for Representation Learning](https://mlsanity.com/paper/1903.11780/) (2019)
- [On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms](https://mlsanity.com/paper/1901.06482/) (2019)
- [Multivariate Rank-based Distribution-free Nonparametric Testing using Measure Transportation](https://mlsanity.com/paper/1909.08733/) (2019)
- [Differentiable Deep Clustering with Cluster Size Constraints](https://mlsanity.com/paper/1910.09036/) (2019)
- [DOTmark - A Benchmark for Discrete Optimal Transport](https://mlsanity.com/paper/1610.03368/) (2016)
- [Entropy Regularized Optimal Transport Independence Criterion](https://mlsanity.com/paper/2112.15265/) (2021)
- [Accelerated Bregman Primal-Dual methods applied to Optimal Transport and Wasserstein Barycenter problems](https://mlsanity.com/paper/2203.00802/) (2022)
- [An Accelerated Stochastic Variance-Reduced Algorithm for Entropic Wasserstein Barycenters](https://mlsanity.com/paper/2203.00813/) (2022)
- [A Study of Performance of Optimal Transport](https://mlsanity.com/paper/2005.01182/) (2020)

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

- [Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods](https://mlsanity.com/paper/2301.13006/) (2023)
- [Fractional Correspondence Framework in Detection Transformer](https://mlsanity.com/paper/2503.04107/) (2025)
- [Accelerated Sinkhorn Algorithms for Partial Optimal Transport](https://mlsanity.com/paper/2601.17196/) (2026)

## Abstract (arXiv)

Computing the empirical Wasserstein distance in the Wasserstein-distance-based independence test is an optimal transport (OT) problem with a special structure. This observation inspires us to study a special type of OT problem and propose a modified Hungarian algorithm to solve it exactly. For the OT problem involving two marginals with m and n atoms (m≥ n), respectively, the computational complexity of the proposed algorithm is O(m2n). Computing the empirical Wasserstein distance in the independence test requires solving this special type of OT problem, where m=n2. The associated computational complexity of the proposed algorithm is O(n5), while the order of applying the classic Hungarian algorithm is O(n6). In addition to the aforementioned special type of OT problem, it is shown that the modified Hungarian algorithm could be adopted to solve a wider range of OT problems. Broader applications of the proposed algorithm are discussed -- solving the one-to-many assignment problem and the many-to-many assignment problem. We conduct numerical experiments to validate our theoretical results. The experiment results demonstrate that the proposed modified Hungarian algorithm compares favorably with the Hungarian algorithm, the well-known Sinkhorn algorithm, and the network simplex algorithm.