I have two sets $A$ and $B$, each containing $N$ high-dimensional vectors. I have an $N\times N$ matrix, $M$, where $M_{i,j}=\text{Dist}||A_i,B_j||$.
I am trying to find a bijective map $A\rightarrow B$ that minimises the average distance between paired elements.
The surjective case is obviously trivial; just map $A_i$ to $B_j$ where $j=\text{argmax}(M_{i,j})$. However I want a 1-to-1 mapping.
$N$ is not very large (~5), but I have many such pairs and need to find an algorithm in order to automate the process.
Any help appreciated!
This is called an Assignment problem. You can formulate you problem as the following integer program:
$$ min \sum_{i=1}^{N}\sum_{j=1}^{N} x_{ij} M_{ij} \\ s.t. \sum_{i=1}^{N}x_{ij} = 1 \;\forall j \in N \\ \sum_{j=1}^{N}x_{ij} = 1 \; \forall i \in N \\ 0 \leq x_{ij} \leq 1 \;\forall i\in N,j \in N \\ x_{ij} \in \mathbb{Z} \;\forall i\in N,j \in N $$
This problem can be solved by solving the linear relaxation of the above IP (drop the integer constraint) with e.g. the Simplex Method.