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.

Do you have any advice?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.