<p>Suppose the <span class="math-container">$X,Y$</span> are sorted.  Then <span class="math-container">$X_1$</span> (the smallest <span class="math-container">$X$</span>-value) must always be matched with <span class="math-container">$Y_1$</span> (the smallest <span class="math-container">$Y$</span>-value).  (Why?  If you consider some other pairing, say one that includes <span class="math-container">$(X_1,Y_j)$</span> and <span class="math-container">$(X_i,Y_1)$</span>, then changing those two pairs to <span class="math-container">$(X_1,Y_1)$</span> and <span class="math-container">$(X_i,Y_j)$</span> yields a lower-cost pairing.  I'll let you prove this.  The case analysis is not too difficult.)</p>
<p>Continuing onward, we see that you can sort the <span class="math-container">$X$</span> and <span class="math-container">$Y$</span> and then match <span class="math-container">$(X_i,Y_i)$</span> for each <span class="math-container">$i$</span>, to obtain the optimal solution.</p>
<p>Thus, the problem can be solved in <span class="math-container">$O(N \log N)$</span> time.</p>

CC BY-SA 4.0
2023-09-25T06:43:52.553Z
2023-09-25T06:43:52.553Z
D.W.
<p>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:</p>
<p>Bonneel, Nicolas, et al. &quot;Sliced and radon wasserstein barycenters of measures.&quot; Journal of Mathematical Imaging and Vision 51 (2015): 22-45.</p>

CC BY-SA 4.0
2023-10-18T16:55:35.060Z
2023-10-18T16:55:35.060Z
calmcc
<p>Suppose I have two sets of real numbers, <span class="math-container">$X$</span> and <span class="math-container">$Y$</span>, each of cardinality <span class="math-container">$N$</span>. I would like to assign these points to pairs <span class="math-container">$(X_i, Y_j)$</span> such that the sum of squared intra-pair distances is minimized. One option is to use the Hungarian algorithm with complexity <span class="math-container">$O(N^3)$</span>, forming a cost matrix with all the squared distances between <span class="math-container">$X$</span> elements and <span class="math-container">$Y$</span> elements. Another option is to solve this approximately in <span class="math-container">$O(N log N)$</span> 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?</p>
<p>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.</p>

<co.combinatorics>
Assignment problem for forming pairs of real numbers
calmcc
# Assignment problem for forming pairs of real numbers

(Asked by: username_0 on 2023-09-24)

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.

**Tags:** co.combinatorics

---

## 2 answers

### Answer by username_1 on 2023-09-25. Score: 2 | Accepted answer

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 by username_0 on 2023-10-18. Score: 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.


---

