TY - GEN
T1 - A Scalable Approximation Algorithm for Weighted Longest Common Subsequence
AU - Buhler, Jeremy
AU - Lavastida, Thomas
AU - Lu, Kefu
AU - Moseley, Benjamin
N1 - Funding Information:
B. Moseley, K. Lu and T. Lavastida were supported in part by a Google Research Award and NSF Grants CCF-1617724, CCF-1733873, and CCF-1725661.
Publisher Copyright:
© 2021, Springer Nature Switzerland AG.
PY - 2021
Y1 - 2021
N2 - This work introduces novel parallel methods for weighted longest common subsequence (WLCS) and its generalization, all-substrings WLCS. Previous work developed efficient algorithms for these problems via Monge matrix multiplication, which is a limiting factor for further improvement. Diverging from these approaches, we relax the algorithm’s optimality guarantee in a controlled way, using a different, natural dynamic program which can be sketched and solved in a divide-and-conquer manner that is efficient to parallelize. Additionally, to compute the base case of our algorithm, we develop a novel and efficient method for all-substrings WLCS inspired by previous work on unweighted all-substrings LCS, exploiting the typically small range of weights. Our method fits in most parallel models of computation, including the PRAM and the BSP model. To the best of our knowledge this is the fastest (1 - ϵ) -approximation algorithm for all-substrings WLCS and WLCS in BSP. Further, this is the asymptotically fastest parallel algorithm for weighted LCS as the number of processors increases.
AB - This work introduces novel parallel methods for weighted longest common subsequence (WLCS) and its generalization, all-substrings WLCS. Previous work developed efficient algorithms for these problems via Monge matrix multiplication, which is a limiting factor for further improvement. Diverging from these approaches, we relax the algorithm’s optimality guarantee in a controlled way, using a different, natural dynamic program which can be sketched and solved in a divide-and-conquer manner that is efficient to parallelize. Additionally, to compute the base case of our algorithm, we develop a novel and efficient method for all-substrings WLCS inspired by previous work on unweighted all-substrings LCS, exploiting the typically small range of weights. Our method fits in most parallel models of computation, including the PRAM and the BSP model. To the best of our knowledge this is the fastest (1 - ϵ) -approximation algorithm for all-substrings WLCS and WLCS in BSP. Further, this is the asymptotically fastest parallel algorithm for weighted LCS as the number of processors increases.
KW - Parallel approximation algorithms
KW - Weighted LCS
UR - http://www.scopus.com/inward/record.url?scp=85115138182&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-85665-6_23
DO - 10.1007/978-3-030-85665-6_23
M3 - Conference contribution
AN - SCOPUS:85115138182
SN - 9783030856649
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 368
EP - 384
BT - Euro-Par 2021
A2 - Sousa, Leonel
A2 - Roma, Nuno
A2 - Tomás, Pedro
PB - Springer Science and Business Media Deutschland GmbH
T2 - 27th International European Conference on Parallel and Distributed Computing, Euro-Par 2021
Y2 - 1 September 2021 through 3 September 2021
ER -