A Linear-Time n 0.4 -Approximation for Longest Common Subsequence

DOI10.1145/3568398arXiv2106.08195OpenAlexW3172736027MaRDI QIDQ6075744

Karl Bringmann, Debarati Das, Vincent Cohen-Addad

Publication date: 23 October 2023

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2106.08195

zbMATH Keywords

approximation algorithmsstring algorithmslongest common subsequence

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new efficient algorithm for computing the longest common subsequence
• An O(NP) sequence comparison algorithm
• Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
• The longest common subsequence problem revisited
• An \(O(ND)\) difference algorithm and its variations
• A faster algorithm computing string edit distances
• A longest common subsequence algorithm suitable for similar text strings
• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
• Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
• A sublinear algorithm for weakly approximating edit distance
• Oblivious string embeddings and edit distance approximations
• 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
• Sparse dynamic programming I
• The String-to-String Correction Problem
• Approximating Edit Distance in Near-Linear Time
• Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
• Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds
• Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time
• Constant-factor approximation of near-linear edit distance in near-linear time
• Constant factor approximations to edit distance on far input pairs in nearly linear time
• Reducing approximate Longest Common Subsequence to approximate Edit Distance
• Approximating LCS in Linear Time: Beating the √n Barrier
• Exact and Efficient Generation of Geometric Random Variates and Random Graphs
• Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made