Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier

DOI10.1137/19M1272068OpenAlexW4293037332MaRDI QIDQ5097510

Xiaorui Sun, Saeedreza Seddighin, Masoud Seddighin, Mohammad Taghi Hajiaghayi

Publication date: 25 August 2022

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/19m1272068

zbMATH Keywords

approximationlinear timelongest common subsequence

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• New tabulation and sparse dynamic programming based techniques for sequence similarity problems
• Computing a longest common subsequence for a set of strings
• The longest common subsequence problem revisited
• A faster algorithm computing string edit distances
• A longest common subsequence algorithm suitable for similar text strings
• Fast and compact regular expression matching
• A decomposition theorem for partially ordered sets
• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
• Oblivious string embeddings and edit distance approximations
• A linear space algorithm for computing maximal common subsequences
• Bounds on the Complexity of the Longest Common Subsequence Problem
• A fast algorithm for computing longest common subsequences
• Algorithms for the Longest Common Subsequence Problem
• Incremental String Comparison
• Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
• Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds
• Longest common subsequences
• Improved Algorithms for Edit Distance and LCS: Beyond Worst Case
• Approximating edit distance in near-linear time
• Massively Parallel Approximation Algorithms for Edit Distance and Longest Common Subsequence
• A Dual of Dilworth's Decomposition Theorem
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS

This page was built for publication: Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier