Discrete Optimal Transport with Independent Marginals is #P-Hard
  We study the computational complexity of the optimal transport problem that
evaluates the Wasserstein distance between the distributions of two
K-dimensional discrete random vectors. The best known algorithms for this
problem run in polynomial time in the maximum of the number of atoms of the two
distributions. However, if the components of either random vector are
independent, then this number can be exponential in K even though the size of
the problem description scales linearly with K. We prove that the described
optimal transport problem is #P-hard even if all components of the first random
vector are independent uniform Bernoulli random variables, while the second
random vector has merely two atoms, and even if only approximate solutions are
sought. We also develop a dynamic programming-type algorithm that approximates
the Wasserstein distance in pseudo-polynomial time when the components of the
first random vector follow arbitrary independent discrete distributions, and we
identify special problem instances that can be solved exactly in strongly
polynomial time.
