An improved lower bound on approximation algorithms for the closest substring problem

DOI10.1016/J.IPL.2007.12.005MaRDI QIDQ963389zbMATH OpenOpenAlexFDO

Authors Jianxin Wang, Min Huang, Jianer Chen

Publication date 19 April 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2007.12.005

zbMATH Keywords

analysis of algorithmsapproximation algorithmscomputational biologylower boundclosest substring problem

Mathematics Subject Classification ID

Computing methodologies and applications (68U99) Approximation algorithms (68W25)

Recommendations

• A Lower Bound on Approximation Algorithms for the Closest Substring Problem
• scientific article; zbMATH DE number 1615273
• Complexity of approximating closest substring problems.
• More efficient algorithms for closest string and substring problems
• Lower bounds for approximation schemes for Closest String

Cites work

• scientific article; zbMATH DE number 1615273 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 2086391 (Why is no real title available?)
• Distinguishing string selection problems.
• On the closest string and substring problems
• On the computational hardness based on linear fpt-reductions
• On the parameterized intractability of motif search problems
• Optimization, approximation, and complexity classes
• Parameterized computation and complexity: a new approach dealing with NP-hardness
• Parameterized intractability of distinguishing substring selection
• Strong computational lower bounds via parameterized complexity
• Which problems have strongly exponential complexity?

Cited in

(7)

• Complexity of approximating closest substring problems.
• Fundamentals of Computation Theory
• A GRASP algorithm for the closest string problem using a probability-based heuristic
• Combinatorial Pattern Matching
• scientific article; zbMATH DE number 1615273 (Why is no real title available?)
• Lower bounds for approximation schemes for Closest String
• A Lower Bound on Approximation Algorithms for the Closest Substring Problem

This page was built for publication: An improved 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 Q963389)