Planar eucliean bipartite matching with squared distances

Question

This is probably a really stupid question, but suppose I have two sets of points in the plane $X$ and $Y$ each with cardinality $|X| = |Y| = n$. For any bipartite matching $M$ between $X$ and $Y$, let $c_1(M)$ denote the total "cost" of the matching $M$, in which we say that the cost between a pair $(x_i,y_j)$ is simply the Euclidean distance between $x_i$ and $y_j$. Similarly let $c_2(M)$ denote the total cost of the matching $M$ where the cost between a pair $(x_i,y_j)$ is the square of the distance between $x_i$ and $y_j$. Let $M_1$ and $M_2$ denote the optimal matchings with respect to cost functions $c_1$ and $c_2$ respectively. My question is: what are the point sets $X$ and $Y$ that maximize the ratio $c_1(M_2)/c_1(M_1)$?

Answer 1

The quotient can get as close as we please to $\sqrt{n}$.

Start by putting a red and a blue point distance $\sqrt{n}$ apart (let me use colors instead of "point in $X$"). Then put $n-1$ pairs of coinciding points (or extremely close if you don't want them to coincide), one red and one blue, as "stepping stones" between them, a unit distance apart, but along a large circular path.

With true distances, a pair of coinciding points of opposite color should always be matched to each other, so $c_1(M_1)=\sqrt{n}$. But with squared distances, the cost of that matching is $n$, so it will be just as good to use the stepping stones and pay for $n$ edges of cost 1 (and strictly better with a slight perturbation of the points).

Provided the stepping stones are arranged so that under squared distances no shortcut will pay, we get $c_1(M_2) = n$.

Clearly $\sqrt{n}$ is the best we can do. If we take the distance $c_1(M_2)$ and chop it into $n$ pieces, then the sum of the squares of the pieces is minimized when they are equal, therefore $$\frac{c_1(M_2)^2}n\leq c_2(M_2) \leq c_2(M_1)\leq c_1(M_1)^2.$$