The Closest Substring problem (CSP), where a short string is sought that minimizes the number of mismatches between it and each of a given set of strings, is a minimization problem with polynomial time approximation schemes. In this paper, a lower bound on approximation algorithms for the CSP problem is developed. We prove that unless the Exponential Time Hypothesis (ETH Hypothesis, i.e., not all search problems in SNP are solvable in subexponential time) fails, the CSP problem has no polynomial time approximation schemes of running time f(1/ε)|x| O(1/?∈?) for any function f, where |x| is the size of input instance. 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 CSP problem for small error bound ε.
展开▼
机译：最接近的子字符串问题（CSP），其中寻求短串最小化它与给定字符串集之间的不匹配的数量，是多项式时间近似方案的最小化问题。在本文中，开发了CSP问题的近似算法的下限。我们证明除非指数时间假设（Eth假设，即SNP中的所有搜索问题在子尺度时间中可解决），否则CSP问题没有运行时的多项式时间近似方案F（1 /ε）| x | O（1 /？∈？）对于任何功能f，其中word | x |是输入实例的大小。这基本上排除了CSP问题具有实际多项式时间近似方案的可能性，即使对于误差ε的中等值也是如此。结果，文献中CSP问题的近似方案的研究不太可能会导致CSP问题的实际近似算法，对于小错误绑定ε。
展开▼
