MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Lower Bounds for Approximation Schemes for Closest String

Michał Pilipczuk
University of Warsaw
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience
English

Date, Time and Location

Tuesday, 14 June 2016
13:00
30 Minutes
E1 4
024
Saarbrücken

Abstract

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, no efficient polynomial-time approximation scheme (EPTAS) has been proposed so far. 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.

Contact

Erik Jan van Leeuwen
--email hidden
passcode not visible
logged in users only

Erik Jan van Leeuwen, 06/09/2016 08:49 -- Created document.