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.