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/
Cygan, Marek ;
Lokshtanov, Daniel ;
Pilipczuk, Marcin ;
Pilipczuk, Michal ;
Saurabh, Saket
Lower Bounds for Approximation Schemes for Closest String
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 |