×

An improved lower bound on approximation algorithms for the closest substring problem. (English) Zbl 1186.68567

Summary: 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 \).

MSC:

68W25 Approximation algorithms
68U99 Computing methodologies and applications
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chen, J., Parameterized computation and complexity: A new approach dealing with NP-hardness, Journal of Computer Science and Technology, 20, 18-37 (2005) · Zbl 1258.68065
[2] Chen, J.; Huang, X.; Kanj, I.; Xia, G., Strong computational lower bounds via parameterized complexity, Journal of Computer and System Sciences, 72, 1346-1367 (2006) · Zbl 1119.68092
[3] Chen, J.; Huang, X.; Kanj, I.; Xia, G., On the computational hardness based on linear FPT-reductions, Journal of Combinatorial Optimization, 11, 231-247 (2006) · Zbl 1130.90064
[4] Downey, R.; Fellows, M., Parameterized Complexity (1999), Springer: Springer New York · Zbl 0961.68533
[5] Fellows, M. R.; Gramm, J.; Niedermeier, R., On the parameterized intractability of Closest Substring and related problems, (STACS 2002. STACS 2002, Lecture Notes in Computer Science, vol. 2285 (2002), Springer), 262-273 · Zbl 1054.68070
[6] Fellows, M. R.; Gramm, J.; Niedermeier, R., On the parameterized intractability of motif search problems, Combinatorica, 26, 141-167 (2006) · Zbl 1109.68049
[7] Gramm, J.; Guo, J.; Niedermeier, R., Parameterized intractability of distinguished substring selection, Theory of Computing Systems, 39, 545-560 (2006) · Zbl 1103.68489
[8] Impagliazzo, R.; Paturi, R.; Zane, F., Which problems have strongly exponential complexity?, Journal of Computer and System Sciences, 63, 512-530 (2001) · Zbl 1006.68052
[9] Kevin Lanctot, J.; Li, M.; Ma, B.; Wang, S.; Zhang, L., Distinguishing string selection problems, Information and Computation, 185, 42-55 (2003) · Zbl 1069.68116
[10] Li, M.; Ma, B.; Wang, L., On the closest string and substring problems, Journal of the ACM, 49, 157-171 (2002) · Zbl 1323.68635
[11] B. Ma, A polynomial time approximation scheme for the closest substring problem, in: Proc. 11th Annual Symposium on Combinatorial Pattern Matching, 2000, pp. 99-107; B. Ma, A polynomial time approximation scheme for the closest substring problem, in: Proc. 11th Annual Symposium on Combinatorial Pattern Matching, 2000, pp. 99-107 · Zbl 0964.68114
[12] D. Marx, The closest substring problem with small distances, in: Proc. 46th Annual IEEE Symp. Foundations of Computer Science (FOCS 2005), 2005, pp. 63-72; D. Marx, The closest substring problem with small distances, in: Proc. 46th Annual IEEE Symp. Foundations of Computer Science (FOCS 2005), 2005, pp. 63-72
[13] Papadimitriou, C.; Yannakakis, M., Optimization, approximation, and complexity classes, Journal of Computer and System Sciences, 43, 425-440 (1991) · Zbl 0765.68036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.