1
$\begingroup$

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?

$\endgroup$
1

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.