An optimization problem, non complete bipartite graph and hungarian algorithm

Question

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 !

Answer 1

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.

Now run the usual algorithm, and the solution will have cost exactly twice the unbalanced cost.

p.s the fact that the graph is not complete is irrelevant - you can always pretend that there are dummy edges with infinite weight.

While the above method works, it's inefficient. there's a recent (2012) paper by Ramshaw and Tarjan on exactly this problem.