On Assignment Problems Related to Gromov-Wasserstein Distances on the Real Line

Abstract

Let $x_1<\cdots <x_n$ and $y_1<\cdots <y_n$, $n\in \mathbb{N}$, be real numbers. We show by an example that the assignment problem $$\underset{\sigma \in S_n}{\max }{F}_{\sigma }(x,y):=\frac{1}{2}\sum _{i,k=1}^n|x_i-x_k{|}^{\alpha }|y_{\sigma (i)}-y_{\sigma (k)}{|}^{\alpha },\alpha >0,$$ is in general neither solved by the identical permutation (id) nor the anti-identical permutation (a-id) if $n>2+2^{\alpha }$. Indeed the above maximum can be, depending on the number of points, arbitrary far away from $F_{\text{id}}(x,y)$ and $F_{\text{a-id}}(x,y)$. The motivation to deal with such assignment problems came from their relation to Gromov-Wasserstein divergences which have recently attained a lot of attention.