# Improve optimization over 'mapping' of indices

I have two tables at my disposal, one work dataset and one reference dataset. Each dataset has got two columns, lets say these are fields A and B. I would like to associate the rows in the reference dataset with the rows in work dataset that are 'closest' w.r.t. some distance. I have more rows in the work dataset than in the reference dataset, and I will match all rows in the reference dataset to some rows in the work dataset.

I can define distance between two rows in the reference and work datasets as:

$d_{i,j} = (A_{w}(i) - A_{r}(j))^{2} + (B_{w}(i) - B_{r}(j))^{2}$

with $A_{w}, A_{r}, B_{w}, B_{r}$ the A and B columns in the work and reference datasets with obvious notation.

In other word, I want to minimize over all permutations of rows from the work dataset (with the same number of rows as in the reference dataset) the sum of distances between one row in reference dataset and one row in work dataset.

I do not know how to proceed other than by brute-force examination of all permutations.

This problem is combinatorial. What about stochastic methods: genetic algorithm, swarm...

Could you hint at some idea for a start?

Thanks!

-
do you want to minimize the distance over all i and j, (so the point in the work data set must be as close as possible to all points in ref) or over certain pairs (such as i=j)? – Godric Seer Nov 29 '12 at 14:16
@GodricSeer i have to map each row in reference dataset to one row in work dataset minimizing sum of distances between associated rows. I have to find the best injection from reference to work dataset. – antitrust Nov 29 '12 at 14:40

If I interpret the problem right, the task is to assign to each $j$ in the column index set $J$ of the distance matrix an index $x_j$ from the row index set $I$ such that the $x_j$ are all different and the $\sum_j d(x_j,j)$ is minimal.