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

Let x1 < dots < xn and y1 < dots < yn, n ∈ mathbb N, be real numbers. We show by an example that the assignment problem maxσ ∈ Sn Fσ(x,y) := frac12 sumi,k=1n |xi - xk|α , |yσ(i) - yσ(k)|α, quad α >0, is in general neither solved by the identical permutation (id) nor the anti-identical permutation (a-id) if n > 2 +2α. Indeed the above maximum can be, depending on the number of points, arbitrary far away from Fid(x,y) and Fa-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.