Approximability of constrained LCS

DOI10.1016/J.JCSS.2011.10.002MaRDI QIDQ439929zbMATH OpenOpenAlexFDO

Authors Minghui Jiang

Publication date 17 August 2012

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2011.10.002

zbMATH Keywords

computational complexityapproximation algorithmscomputational biologylongest common subsequence

Mathematics Subject Classification ID

Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Algorithms on strings (68W32)

Recommendations

• Approximability of constrained LCS
• Constrained LCS: Hardness and Approximation
• Variants of constrained longest common subsequence
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
• Approximating LCS in Linear Time: Beating the √n Barrier

Cites work

• A simple algorithm for the constrained sequence problems
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Combined super-/substring and super-/subsequence problems
• Constrained LCS: Hardness and Approximation
• Linear degree extractors and the inapproximability of max clique and chromatic number
• New efficient algorithms for the LCS and constrained LCS problems
• On finding minimal, maximal, and consistent sequences over a binary alphabet
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• On the generalized constrained longest common subsequence problems
• The Complexity of Some Problems on Subsequences and Supersequences
• The constrained longest common subsequence problem
• Variants of constrained longest common subsequence

Cited in

(10)

• A much better polynomial time approximation of consistency in the LR calculus
• Logic Programming and Nonmonotonic Reasoning
• Perfect LRCs and \(k\)-optimal LRCs
• Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds
• Limit Behavior of Locally Consistent Constraint Satisfaction Problems
• Approximating LCS in Linear Time: Beating the √n Barrier
• Approximability of constrained LCS
• Constrained LCS: Hardness and Approximation
• Lower bounds for constant query affine-invariant LCCs and LTCs
• Approximating longest common subsequence in linear time: beating the \(\sqrt{n}\) barrier

This page was built for publication: Approximability of constrained LCS

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