For one of my works, I need a "minimum distance bipartite matching" algorithm, which I describe below:
I have two disjoint sets $A$ and $B$ with $|A| = |B| = n$. The sets $A$ and $B$ are subsets of $\mathbb{R}^d$ for some $d \geq 1$ and I want to match each point $a$ in $A$ to a unique point $m(a)$ in $B$ (so $m$ is a bijection from $A$ to $B$). I then want to solve the following minimization problem: $$\arg \min_{m:A \mapsto B, ~\mathrm{bijection}} \sum_{a\in A}||a-m(a)||_2~,$$ where $||\cdot||_2$ denotes the $L^2$ norm.
My question is, is there an efficient algorithm to do this, other than the naive way of checking through all the $n!$ many permutations? If so, is there an inbuilt code in MATLAB or R which does exactly this?
This is a minimum (equivalently maximum) weight bipartite matching problem where the weight of edge $am(a)$ is $||a-m(a)||_2$. An example of code to solve this is here, although there will be various others, possibly in the languages you are looking for.