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

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 (m²n). Computing the empirical Wasserstein distance in the independence test requires solving this special type of OT problem, where m = n². The associated computational complexity of the proposed algorithm is O (n⁵), while the order of applying the classic Hungarian algorithm is O (n⁶). 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.