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

abstract

• 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 / ) no (1 / ) 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 . 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 . 2007 Elsevier B.V. All rights reserved.

authors

• Chen, Jianer

published proceedings

• Information Processing Letters

author list (cited authors)

• Wang, J., Chen, J., & Huang, M.

citation count

• 6

complete list of authors

• Wang, Jianxin||Chen, Jianer||Huang, Min

publication date

• June 2008

publisher

• Elsevier  Publisher

published in

• Information Processing Letters  Journal

Digital Object Identifier (DOI)

• 10.1016/j.ipl.2007.12.005

start page

• 24

end page

• 28

volume

• 107

issue

• 1

URL

• http%3A%2F%2Fdx.doi.org%2F10.1016%2Fj.ipl.2007.12.005