Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.16
URN: urn:nbn:de:0030-drops-112319
URL: https://drops.dagstuhl.de/opus/volltexte/2019/11231/
Allender, Eric ; Farach-Colton, Martín ; Tsai, Meng-Tsung
Syntactic Separation of Subset Satisfiability Problems
| pdf-format: |
|
Abstract
Variants of the Exponential Time Hypothesis (ETH) have been used to derive lower bounds on the time complexity for certain problems, so that the hardness results match long-standing algorithmic results. In this paper, we consider a syntactically defined class of problems, and give conditions for when problems in this class require strongly exponential time to approximate to within a factor of (1-epsilon) for some constant epsilon > 0, assuming the Gap Exponential Time Hypothesis (Gap-ETH), versus when they admit a PTAS. Our class includes a rich set of problems from additive combinatorics, computational geometry, and graph theory. Our hardness results also match the best known algorithmic results for these problems.
BibTeX - Entry
@InProceedings{allender_et_al:LIPIcs:2019:11231,
author = {Eric Allender and Mart{\'\i}n Farach-Colton and Meng-Tsung Tsai},
title = {{Syntactic Separation of Subset Satisfiability Problems}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {16:1--16:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11231},
URN = {urn:nbn:de:0030-drops-112319},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.16},
annote = {Keywords: Syntactic Class, Exponential Time Hypothesis, APX, PTAS}
}
| Keywords: | Syntactic Class, Exponential Time Hypothesis, APX, PTAS | |
| Seminar: | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) | |
| Issue date: | 2019 | |
| Date of publication: | 17.09.2019 |
