The ultrametric Gromov-Wasserstein distance

Abstract

In this paper, we investigate compact ultrametric measure spaces which form a subset ${\mathcal{U}}^w$ of the collection of all metric measure spaces ${\mathcal{M}}^w$. Similar as for the ultrametric Gromov-Hausdorff distance on the collection of ultrametric spaces $\mathcal{U}$, we define ultrametric versions of two metrics on ${\mathcal{U}}^w$, namely of Sturm's distance of order $p$ and of the Gromov-Wasserstein distance of order $p$. We study the basic topological and geometric properties of these distances as well as their relation and derive for $p=\infty$ a polynomial time algorithm for their calculation. Further, several lower bounds for both distances are derived and some of our results are generalized to the case of finite ultra-dissimilarity spaces.