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)$?

  • 1
    $\begingroup$ In other words, if you compute the minimum matching, and then realize you forgot to take square roots when tabulating the distances, how far off the mark can you be? $\endgroup$ – Johan Wästlund Sep 30 '12 at 7:47

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.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.