In the Closest String problem one is given a family S of equal-length strings over some fixed alphabet, and the task is to find a string y that minimizes the maximum Hamming distance between y and a string from S. While polynomial-time approximation schemes (PTASes) for this problem are known for a long time [Li et al.; J. ACMu2702], no efficient polynomial-time approximation scheme (EPTAS) has been proposed so far. In this paper, we prove that the existence of an EPTAS for Closest String is in fact unlikely, as it would imply that FPT=W[1], a highly unexpected collapse in the hierarchy of parameterized complexity classes. Our proof also shows that the existence of a PTAS for Closest String with running time f(eps) n^o(1/eps), for any computable function f, would contradict the Exponential Time Hypothesis.
展开▼
机译：在“最接近的字符串”问题中，给定一个固定长度的字母，在一些固定字母上的族S，其任务是找到一个字符串y，该字符串最小化y和S的字符串之间的最大汉明距离。多项式时间近似方案解决该问题的方法（PTASes）由来已久[Li et al .; J. ACM u2702]，到目前为止，尚未提出有效的多项式时间近似方案（EPTAS）。在本文中，我们证明了“最接近的字符串”的EPTAS的存在实际上是不可能的，因为这暗示着FPT = W [1]，这是参数化复杂性类的层次结构中非常出乎意料的崩溃。我们的证据还表明，对于任何可计算函数f，最短字符串的PTAS的运行时间为f（eps）n ^ o（1 / eps）的存在将与指数时间假说相矛盾。
展开▼
