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.APPROX-RANDOM.2019.16
URN: urn:nbn:de:0030-drops-112319
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11231/
Go to the corresponding LIPIcs Volume Portal

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

Syntactic Separation of Subset Satisfiability Problems

pdf-format:
LIPIcs-APPROX-RANDOM-2019-16.pdf (0.6 MB)

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
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Issue Date: 2019
Date of publication: 17.09.2019

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