A Scalable Approximation Algorithm for Weighted Longest Common Subsequence

Autor:	Thomas Lavastida, Benjamin Moseley, Jeremy Buhler, Kefu Lu
Rok vydání:	2021
Předmět:	Longest common subsequence problem Limiting factor Computer science Generalization Efficient algorithm Scalability Approximation algorithm Algorithm Matrix multiplication
Zdroj:	Euro-Par 2021: Parallel Processing ISBN: 9783030856649 Euro-Par
DOI:	10.1007/978-3-030-85665-6_23
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::6e1bc2c4f395b26a943d6078f25a91ea https://doi.org/10.1007/978-3-030-85665-6_23 Zobrazit plný text záznamu