# An optimization problem, non complete bipartite graph and hungarian algorithm

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 the rows in reference dataset with the rows in work dataset that are 'closest' w.r.t. some distance. I have more rows in work dataset than in reference dataset, and i will match all rows in reference dataset to some rows in work dataset.

I can define distance between two rows in reference and wrk dataset like this:

$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 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 reference dataset) the sum of distances between one row in reference dataset and one row in wrk dataset.

I do not know how to proceed if not examining all permutations.

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

Could you hint at some idea for a start ?

I had a look at linear assignment problem. However, my problem is not a complete bipartatite graph representation, it is not complete since there can be more peaks in work signal than there are in reference signal.

Thanks !

-

There's a standard trick to convert the min cost matching problem on a balanced bipartite graph to one on an unbalanced bipartite graph. Let $G = (X \cup Y, E, w)$ be the bipartite graph where $E \subset X \times Y$ and $|X| \le |Y|$.
Now create a copy of $G$ and add it "reversed", so that in the new graph both sides have exactly $|X| + |Y|$ vertices. All old edges have their same weight: edges between vertices in $X$ and their copies have weight $\infty$, and edges between vertices in $Y$ and their copies have weight zero.