2026-10-06T01:31:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6023 2024-03-06T09:37:29Z ddc:004 open_access

Lower Bounds for Approximation Schemes for Closest String Cygan, Marek Lokshtanov, Daniel Pilipczuk, Marcin Pilipczuk, Michal Saurabh, Saket closest string PTAS efficient PTAS 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. ACM'02], 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marek Cygan and Daniel Lokshtanov and Marcin Pilipczuk and Michal Pilipczuk and Saket Saurabh 2016 Is Part Of LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2016.12 urn:nbn:de:0030-drops-60232 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.12 eng https://creativecommons.org/licenses/by/3.0/legalcode