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

DOI10.1016/J.IPL.2007.12.005zbMATH Open1186.68567OpenAlexW1965524011MaRDI QIDQ963389FDOQ963389

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

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

zbMATH Keywords

analysis of algorithmsapproximation algorithmscomputational biologylower boundclosest substring problem

Mathematics Subject Classification ID

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

Cites Work

• Optimization, approximation, and complexity classes
• Distinguishing string selection problems.
• Which problems have strongly exponential complexity?
• On the closest string and substring problems
• On the parameterized intractability of motif search problems
• Parameterized intractability of distinguishing substring selection
• Title not available (Why is that?)
• Strong computational lower bounds via parameterized complexity
• On the computational hardness based on linear fpt-reductions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Parameterized computation and complexity: a new approach dealing with NP-hardness

Cited In (6)

• Complexity of approximating closest substring problems.
• A GRASP algorithm for the closest string problem using a probability-based heuristic
• Fundamentals of Computation Theory
• Combinatorial Pattern Matching
• A Lower Bound on Approximation Algorithms for the Closest Substring Problem
• Title not available (Why is that?)

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)