Exponential-Time Approximation Algorithms for MAX-SAT: Correlations and Implications
Sixue Liu · arXiv (Cornell University) · 2018
We provide three different algorithms for MAX-SAT approximation. Each of them runs in time $c^n$, where $c < 2$ depends on performance ratio and $n$ is the number of variables in the formula. We show how to correlate them to achieve tighter upper bounds. The results include some worst-case upper bounds for a number of NP-hard problems. Our method also implies a transformation to some MAX SNP-complete problems from their approximations, such that an exponential improvement on upper bounds for the former problem also induces an exponential improvement on the latter one, assuming the Exponential-Time Hypothesis holds.