Approximating longest common subsequence in linear time: beating the n barrier

DOI10.1137/19M1272068MaRDI QIDQ5097510zbMATH OpenOpenAlexFDO

Authors Masoud Seddighin, Saeedreza Seddighin, Xiaorui Sun, Mohammad T. 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)

Recommendations

• Approximating LCS in Linear Time: Beating the √n Barrier
• Approximability of constrained LCS
• Approximability of constrained LCS
• Constrained LCS: Hardness and Approximation
• LCS approximation via embedding into locally non-repetitive strings

Cites work

• A decomposition theorem for partially ordered sets
• A Dual of Dilworth's Decomposition Theorem
• A fast algorithm for computing longest common subsequences
• A faster algorithm computing string edit distances
• A linear space algorithm for computing maximal common subsequences
• A longest common subsequence algorithm suitable for similar text strings
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
• Algorithms for the Longest Common Subsequence Problem
• Approximating edit distance in near-linear time
• Approximating edit distance in truly subquadratic time: quantum and MapReduce
• Bounds on the Complexity of the Longest Common Subsequence Problem
• Computing a longest common subsequence for a set of strings
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• Fast and compact regular expression matching
• Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds
• scientific article; zbMATH DE number 1615278 (Why is no real title available?)
• scientific article; zbMATH DE number 3126094 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• Improved Algorithms for Edit Distance and LCS: Beyond Worst Case
• Incremental String Comparison
• Longest common subsequences
• Massively parallel approximation algorithms for edit distance and longest common subsequence
• New tabulation and sparse dynamic programming based techniques for sequence similarity problems
• Oblivious string embeddings and edit distance approximations
• Polylogarithmic approximation for edit distance and the asymmetric query complexity
• The longest common subsequence problem revisited
• Towards hardness of approximation for polynomial time problems

Cited in

(7)

• Why is it hard to beat \(O(n^2)\) for longest common weakly increasing subsequence?
• LCS Approximation via Embedding into Local Non-repetitive Strings
• Towards hardness of approximation for polynomial time problems
• Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds
• Approximating LCS in Linear Time: Beating the √n Barrier
• Massively parallel approximation algorithms for edit distance and longest common subsequence
• LCS approximation via embedding into locally non-repetitive strings

This page was built for publication: Approximating longest common subsequence in linear time: beating the \(\sqrt{n}\) barrier

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5097510)