Syntactic separation of subset satisfiability problems

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

研究成果: Conference contribution同行評審

摘要

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.

原文English
主出版物標題Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019
編輯Dimitris Achlioptas, Laszlo A. Vegh
發行者Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN(電子)9783959771252
DOIs
出版狀態Published - 9月 2019
事件22nd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 23rd International Conference on Randomization and Computation, APPROX/RANDOM 2019 - Cambridge, United States
持續時間: 20 9月 201922 9月 2019

出版系列

名字Leibniz International Proceedings in Informatics, LIPIcs
145
ISSN(列印)1868-8969

Conference

Conference22nd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 23rd International Conference on Randomization and Computation, APPROX/RANDOM 2019
國家/地區United States
城市Cambridge
期間20/09/1922/09/19

指紋

深入研究「Syntactic separation of subset satisfiability problems」主題。共同形成了獨特的指紋。

引用此