A Scalable Approximation Algorithm for Weighted Longest Common Subsequence
Published in International European Conference on Parallel and Distributed Computing (EURO-PAR), 2021
This paper gives an efficient parallel approximation algorithm for the weighted longest common subsequence problem. This is accomplished by developing an efficient parallelizable dynamic programming algorithm which can be implemented in a divide-and-conquer fashion and an efficient algorithm for all-substrings weighted longest common subsequence which serves as a base case.