Syntactic separation of subset satisfiability problems

Eric Allender, Martín Farach-Colton, Meng Tsung Tsai

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 − ε) 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.

Original languageEnglish
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019
EditorsDimitris Achlioptas, Laszlo A. Vegh
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771252
DOIs
StatePublished - Sep 2019
Event22nd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 23rd International Conference on Randomization and Computation, APPROX/RANDOM 2019 - Cambridge, United States
Duration: 20 Sep 201922 Sep 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume145
ISSN (Print)1868-8969

Conference

Conference22nd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 23rd International Conference on Randomization and Computation, APPROX/RANDOM 2019
CountryUnited States
CityCambridge
Period20/09/1922/09/19

Keywords

  • APX
  • Exponential time hypothesis
  • PTAS
  • Syntactic class

Fingerprint Dive into the research topics of 'Syntactic separation of subset satisfiability problems'. Together they form a unique fingerprint.

  • Cite this

    Allender, E., Farach-Colton, M., & Tsai, M. T. (2019). Syntactic separation of subset satisfiability problems. In D. Achlioptas, & L. A. Vegh (Eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019 [16] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 145). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.16