# Minimum effort merging of two sets

I have the following problem.

I have two sequences of elements $A = [a_1,a_2,\cdots,a_n]$ and $B = [b_1,b_2,\cdots,b_m]$. I can build a matrix $D[n \times m]$ where $d_{ij} = d(a_i,b_j)$

My greedy merging algorithm works as follows:

• For each iteration it takes the shortest distance pair and merges them.
• Then all the distances are recomputed (considering the merged pair)
• The process is repeated until each element of the two sequences is merged.
• Every time I merge a pair, I sum their distance. The final value of the algorithm is the total sum.

Now, I have to run it on a very large set of sequences. I would like to have a fast, parallel, algorithm that provides an approximation or an upper bound of the sum.

I looked for eigenvector techniques, but I could not find any suitable algorithm.