  We propose a numerical algorithm for the computation of multi-marginal
optimal transport (MMOT) problems involving general measures that are not
necessarily discrete. By developing a relaxation scheme in which marginal
constraints are replaced by finitely many linear constraints and by proving a
specifically tailored duality result for this setting, we approximate the MMOT
problem by a linear semi-infinite optimization problem. Moreover, we are able
to recover a feasible and approximately optimal solution of the MMOT problem,
and its sub-optimality can be controlled to be arbitrarily close to 0 under
mild conditions. The developed relaxation scheme leads to a numerical algorithm
which can compute a feasible approximate optimizer of the MMOT problem whose
theoretical sub-optimality can be chosen to be arbitrarily small. Besides the
approximate optimizer, the algorithm is also able to compute both an upper
bound and a lower bound on the optimal value of the MMOT problem. The
difference between the computed bounds provides an explicit upper bound on the
sub-optimality of the computed approximate optimizer. Through a numerical
example, we demonstrate that the proposed algorithm is capable of computing a
high-quality solution of an MMOT problem involving as many as 50 marginals
along with an explicit estimate of its sub-optimality that is much less
conservative compared to the theoretical estimate.
