On the Complexity of Approximating Multimarginal Optimal Transport
  We study the complexity of approximating the multimarginal optimal transport
(MOT) distance, a generalization of the classical optimal transport distance,
considered here between $m$ discrete probability distributions supported each
on $n$ support points. First, we show that the standard linear programming (LP)
representation of the MOT problem is not a minimum-cost flow problem when $m
\geq 3$. This negative result implies that some combinatorial algorithms, e.g.,
network simplex method, are not suitable for approximating the MOT problem,
while the worst-case complexity bound for the deterministic interior-point
algorithm remains a quantity of $\tilde{O}(n^{3m})$. We then propose two simple
and \textit{deterministic} algorithms for approximating the MOT problem. The
first algorithm, which we refer to as \textit{multimarginal Sinkhorn}
algorithm, is a provably efficient multimarginal generalization of the Sinkhorn
algorithm. We show that it achieves a complexity bound of
$\tilde{O}(m^3n^m\varepsilon^{-2})$ for a tolerance $\varepsilon \in (0, 1)$.
This provides a first \textit{near-linear time} complexity bound guarantee for
approximating the MOT problem and matches the best known complexity bound for
the Sinkhorn algorithm in the classical OT setting when $m = 2$. The second
algorithm, which we refer to as \textit{accelerated multimarginal Sinkhorn}
algorithm, achieves the acceleration by incorporating an estimate sequence and
the complexity bound is $\tilde{O}(m^3n^{m+1/3}\varepsilon^{-4/3})$. This bound
is better than that of the first algorithm in terms of $1/\varepsilon$, and
accelerated alternating minimization
algorithm~\citep{Tupitsa-2020-Multimarginal} in terms of $n$. Finally, we
compare our new algorithms with the commercial LP solver \textsc{Gurobi}.
Preliminary results on synthetic data and real images demonstrate the
effectiveness and efficiency of our algorithms.
