A Lower Bound on Approximation Algorithms for the Closest Substring Problem

DOI10.1007/978-3-540-73556-4_31MaRDI QIDQ3611982zbMATH OpenOpenAlexFDO

Authors Jianxin Wang, Min Huang, Jianer Chen

Publication date 3 March 2009

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73556-4_31

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Biochemistry, molecular biology (92C40) Protein sequences, DNA sequences (92D20)

Recommendations

• An improved lower bound on approximation algorithms for the closest substring problem
• Complexity of approximating closest substring problems.
• scientific article; zbMATH DE number 1615273
• Lower bounds for approximation schemes for Closest String
• More efficient algorithms for closest string and substring problems

Cited in

(6)

• LP-based heuristics for the distinguishing string and substring selection problems
• scientific article; zbMATH DE number 1615273 (Why is no real title available?)
• Lower bounds for approximation schemes for Closest String
• Fundamentals of Computation Theory
• Complexity of approximating closest substring problems.
• An improved lower bound on approximation algorithms for the closest substring problem

This page was built for publication: A Lower Bound on Approximation Algorithms for the Closest Substring Problem

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