Deutsch
 
Benutzerhandbuch Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Forschungspapier

Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS

MPG-Autoren
/persons/resource/persons44182

Bringmann,  Karl
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons225687

Ray Chaudhury,  Bhaskar
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

arXiv:1810.01238.pdf
(Preprint), 606KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Bringmann, K., & Ray Chaudhury, B. (2018). Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS. Retrieved from http://arxiv.org/abs/1810.01238.


Zitierlink: http://hdl.handle.net/21.11116/0000-0002-57B9-C
Zusammenfassung
We study sketching and streaming algorithms for the Longest Common Subsequence problem (LCS) on strings of small alphabet size $|\Sigma|$. For the problem of deciding whether the LCS of strings $x,y$ has length at least $L$, we obtain a sketch size and streaming space usage of $\mathcal{O}(L^{|\Sigma| - 1} \log L)$. We also prove matching unconditional lower bounds. As an application, we study a variant of LCS where each alphabet symbol is equipped with a weight that is given as input, and the task is to compute a common subsequence of maximum total weight. Using our sketching algorithm, we obtain an $\mathcal{O}(\textrm{min}\{nm, n + m^{{\lvert \Sigma \rvert}}\})$-time algorithm for this problem, on strings $x,y$ of length $n,m$, with $n \ge m$. We prove optimality of this running time up to lower order factors, assuming the Strong Exponential Time Hypothesis.