Solving a Special Type of Optimal Transport Problem by a Modified Hungarian Algorithm. (arXiv:2210.16645v1 [math.OC])

We observe that computing empirical Wasserstein distance in the 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 an OT problem between
marginals with $m$ and $n$ atoms ($m\geq n$), the computational complexity of
the proposed algorithm is $O(m^2n)$. Computing the empirical Wasserstein
distance in the independence test requires solving this special type of …

algorithm arxiv hungarian math transport type