Lower bounds for approximation schemes for Closest String

DOI10.4230/LIPICS.SWAT.2016.12MaRDI QIDQ5369514zbMATH OpenOpenAlexFDO

Authors Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh

Publication date 17 October 2017

Full work available at URL https://arxiv.org/abs/1509.05809

zbMATH Keywords

closest stringefficient PTASPTAS

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Algorithms on strings (68W32)

Abstract: In the Closest String problem one is given a family $mathcalS$ 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 $mathcalS$. 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 $mathrmFPT=mathrmW[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(varepsilon)cdot{n}^{o(1/varepsilon)}$, for any computable function $f$, would contradict the Exponential Time Hypothesis.

Recommendations

• A Lower Bound on Approximation Algorithms for the Closest Substring Problem
• An improved lower bound on approximation algorithms for the closest substring problem
• scientific article; zbMATH DE number 1615273
• More efficient algorithms for closest string and substring problems
• A three-string approach to the closest string problem

Cited in

(13)

• A new distance metric on strings computable in linear time
• Best approximations of fitness functions of binary strings
• Polynomial time approximation schemes for all 1-center problems on metric rational set similarities
• The complexity of binary matrix completion under diameter constraints
• Consensus patterns (probably) has no EPTAS
• A Lower Bound on Approximation Algorithms for the Closest Substring Problem
• On computing centroids according to the p-norms of Hamming distance vectors
• Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
• Randomized and Parameterized Algorithms for the Closest String Problem
• Parameterized Complexity Analysis for the Closest String with Wildcards Problem
• Slightly superexponential parameterized problems
• Low-Rank Binary Matrix Approximation in Column-Sum Norm.
• An improved lower bound on approximation algorithms for the closest substring problem

This page was built for publication: Lower bounds for approximation schemes for Closest String

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5369514)