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(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.