License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2016.12
URN: urn:nbn:de:0030-drops-60232
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6023/
Go to the corresponding LIPIcs Volume Portal

Cygan, Marek ; Lokshtanov, Daniel ; Pilipczuk, Marcin ; Pilipczuk, Michal ; Saurabh, Saket

Lower Bounds for Approximation Schemes for Closest String

pdf-format:
LIPIcs-SWAT-2016-12.pdf (0.5 MB)

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 [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.

BibTeX - Entry

@InProceedings{cygan_et_al:LIPIcs:2016:6023,
  author =	{Marek Cygan and Daniel Lokshtanov and Marcin Pilipczuk and Michal Pilipczuk and Saket Saurabh},
  title =	{{Lower Bounds for Approximation Schemes for Closest String}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{12:1--12:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Rasmus Pagh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6023},
  URN =		{urn:nbn:de:0030-drops-60232},
  doi =		{10.4230/LIPIcs.SWAT.2016.12},
  annote =	{Keywords: closest string, PTAS, efficient PTAS}
}

Keywords: closest string, PTAS, efficient PTAS
Collection: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Issue Date: 2016
Date of publication: 22.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI