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

Let x1 < \cdot \cdot \cdot < xn and y1 < \cdot \cdot \cdot < yn, n \in N, be real numbers. We show by an example that the assignment problem max \sigma\in Sn \sumn 1 F\sigma(x, y) := 2 i,k =1 lxi -xkl\alphaly\sigma(i) -y\sigma(k)l\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, arbitrarily far away from Fid(x, y) and FFid(x, y). The motivation to deal with such assignment problems came from their relation to Gromov-Wasserstein distances, which have recently received a lot of attention in imaging and shape analysis.