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

DOI10.1016/j.ipl.2007.12.005zbMath1186.68567OpenAlexW1965524011MaRDI QIDQ963389

Min Huang, Jianxin Wang, Jian'er 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 algorithmslower boundcomputational biologyapproximation algorithmsclosest substring problem

Mathematics Subject Classification ID

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

Related Items (1)

A GRASP algorithm for the closest string problem using a probability-based heuristic

Cites Work

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

This page was built for publication: An improved lower bound on approximation algorithms for the closest substring problem