An improved lower bound on approximation algorithms for the Closest Substring problem

作者：Wang Jianxin^*; Chen Jianer; Huang Min

来源：Information Processing Letters, 2008, 107(1): 24-28.

DOI：10.1016/j.ipl.2007.12.005

• analysis of algorithms
• approximation algorithms
• Closest Substring problem
• lower bound
• computational biology

The Closest Substring problem (the CSP problem) is a basic NP-hard problem in the study of computational biology. It is known that the problem has polynomial time approximation schemes. In this paper, we prove that unless the Exponential Time Hypothesis fails, the CSP problem has no polynomial time approximation schemes of running time f(1/epsilon)n(o(1/epsilon)) for any function f. This essentially excludes the possibility that the CSP problem has a practical polynomial time approximation scheme even for moderate values of the error bound epsilon. As a consequence, it is unlikely that the study of approximation schemes for the CSP problem in the literature would lead to practical approximation algorithms for the problem for small error bound epsilon.

• 出版日期2008-6-30
• 单位中南大学