Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Lower Bounds for Approximation Schemes for Closest String
Speaker:Michał Pilipczuk
coming from:University of Warsaw
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 14 June 2016
Duration:30 Minutes
Building:E1 4
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.
Name(s):Erik Jan van Leeuwen
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
Created by:Erik Jan van Leeuwen, 06/09/2016 08:49 AMLast modified by:Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Erik Jan van Leeuwen, 06/09/2016 08:49 AM -- Created document.