TY - GEN
T1 - Syntactic separation of subset satisfiability problems
AU - Allender, Eric
AU - Farach-Colton, Martín
AU - Tsai, Meng Tsung
N1 - Publisher Copyright:
© Eric Allender, Martín Farach-Colton, and Meng-Tsung Tsai.
PY - 2019/9
Y1 - 2019/9
N2 - 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 − ε) for some constant ε > 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.
AB - 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 − ε) for some constant ε > 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.
KW - APX
KW - Exponential time hypothesis
KW - PTAS
KW - Syntactic class
UR - http://www.scopus.com/inward/record.url?scp=85072864802&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85072864802&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.APPROX-RANDOM.2019.16
DO - 10.4230/LIPIcs.APPROX-RANDOM.2019.16
M3 - Conference contribution
AN - SCOPUS:85072864802
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019
A2 - Achlioptas, Dimitris
A2 - Vegh, Laszlo A.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 22nd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 23rd International Conference on Randomization and Computation, APPROX/RANDOM 2019
Y2 - 20 September 2019 through 22 September 2019
ER -