A Linear-Time n 0.4 -Approximation for Longest Common Subsequence
From MaRDI portal
Publication:6075744
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
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
