points matching minimizing sum of square distances I have $2$ sets of $n$ points in $\mathbb{R}^d$ $A$ and $B$.
I am trying to find a bijective function $f:[n]\rightarrow[n]$ such that
$$\sum_{i=1}^n{||A_i-B_{f(i)}}||_2^2$$
is minimized, i.e., to find a pairing between the sets that minimize the sum of square distances.
I thought of using the Hungarian Method which takes $O\left(n^3\right)$ time but is there any way to do it faster? I was looking for papers that try to do it faster but all I could find is papers that talks about minimizing sum of distances instead of square distances.
Is there any way to do it faster than $O\left(n^3\right)$ and either get an optimal solution or a solution with a provable cost of at most $(1+\epsilon)$OPT, where OPT is the optimal cost?
 A: What you're looking for is called the $2$-Wasserstein distance between your sets of points.
The Hungarian method (also named (Khun-)Munkres, depending on the paper) has long been used to solve this exactly, but auction methods converge really fast.
Moreover, in $\mathbb R^d$ with low dimension, you can even use kd-tree methods to make local requests and accelerate the computation. You can see this in a paper (here the sets of points $A$ and $B$ are in a space a little more complicated than $\mathbb R^2$, but you could forget about that and the paper is quite clear). The complexity is hard to estimate because it depends on the heuristic on which the auction method is based, but the paper regress their method's speed to $O(n^{1.6})$. In dimension $d > 2$ it might be a little less efficient but it's better than $O(n^3)$ anyway.
A: For the linear assignment problem, the cost function is arbitrary and specified by an $n \times n$ matrix with entries $c_{i,j}$ that can represent distances or squared distances or anything else. The binary decision variable $x_{i,j}$ indicates whether point $i$ is matched to point $j$, and the problem is to minimize $\sum_{i,j} c_{i,j} x_{i,j}$ subject to
\begin{align}
\sum_j x_{i,j} &= 1 &&\text{for all $i$}\\
\sum_i x_{i,j} &= 1 &&\text{for all $j$}\\
\end{align}
This problem is linear even if the input costs arise from highly nonlinear functions.
