On the complexity of the optimal transport problem with graph-structured
  cost
  Multi-marginal optimal transport (MOT) is a generalization of optimal
transport to multiple marginals. Optimal transport has evolved into an
important tool in many machine learning applications, and its multi-marginal
extension opens up for addressing new challenges in the field of machine
learning. However, the usage of MOT has been largely impeded by its
computational complexity which scales exponentially in the number of marginals.
Fortunately, in many applications, such as barycenter or interpolation
problems, the cost function adheres to structures, which has recently been
exploited for developing efficient computational methods. In this work we
derive computational bounds for these methods. With $m$ marginal distributions
supported on $n$ points, we provide a $ \mathcal{\tilde O}(d(G)m
n^2\epsilon^{-2})$ bound for a $\epsilon$-accuracy when the problem is
associated with a tree with diameter $d(G)$. For the special case of the
Wasserstein barycenter problem, which corresponds to a star-shaped tree, our
bound is in alignment with the existing complexity bound for it.
