Assignment problem for forming pairs of real numbers

Question

Suppose I have two sets of real numbers, $X$ and $Y$, each of cardinality $N$. I would like to assign these points to pairs $(X_i, Y_j)$ such that the sum of squared intra-pair distances is minimized. One option is to use the Hungarian algorithm with complexity $O(N^3)$, forming a cost matrix with all the squared distances between $X$ elements and $Y$ elements. Another option is to solve this approximately in $O(N log N)$ using a K-D tree. But is there any method that is faster than cubic (perhaps quadratic) but better than the K-D tree approach?

The fact that these are one-dimensional real numbers suggests we could somehow exploit the fact that we can sort the numbers. For example, we could sort each set of numbers and pair the elements with the same rank order. If this makes things any easier, I don't need to work with squared distances necessarily; sum of absolute distances would work too.

Answer 1

Suppose the $X,Y$ are sorted. Then $X_1$ (the smallest $X$-value) must always be matched with $Y_1$ (the smallest $Y$-value). (Why? If you consider some other pairing, say one that includes $(X_1,Y_j)$ and $(X_i,Y_1)$, then changing those two pairs to $(X_1,Y_1)$ and $(X_i,Y_j)$ yields a lower-cost pairing. I'll let you prove this. The case analysis is not too difficult.)

Continuing onward, we see that you can sort the $X$ and $Y$ and then match $(X_i,Y_i)$ for each $i$, to obtain the optimal solution.

Thus, the problem can be solved in $O(N \log N)$ time.

Answer 2

It turns out the sorting idea is at the core of the sliced Wasserstein distance for approximating the true Wasserstein distance (which requires either solving a linear assignment problem or running the Sinkhorn algorithm) with 1d projections. See the following paper for more details:

Bonneel, Nicolas, et al. "Sliced and radon wasserstein barycenters of measures." Journal of Mathematical Imaging and Vision 51 (2015): 22-45.