Approximability of constrained LCS

DOI10.1016/J.JCSS.2011.10.002zbMATH Open1244.68036OpenAlexW2001332692MaRDI QIDQ439929FDOQ439929

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

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

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)

Cites Work

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

Cited In (10)

• A much better polynomial time approximation of consistency in the LR calculus
• Logic Programming and Nonmonotonic Reasoning
• Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds
• Perfect LRCs and \(k\)-optimal LRCs
• 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)