For the MAX-E3SAT define $k=\sum_i^n (g_i-1)$, where $n$ is the number of variables and $g_i=\text{max}(\{\text{occurrences of }x_i, \text{occurrences of }\neg x_i\}), \text{ for each }i=\{1,\ldots,n\}$.

We were able to prove a reduction from MAX-E3SAT to a particular minimization problem $\Pi$, wherein if a $\beta$ fraction of the $m$ clauses are satisfied then the cost of the tour is $c_1 k + c_2 (1-\beta) m $, where $c_1, c_2 >0$ are constants.

What are the existing results on MAX E3SAT we could use to show inapproximability? The inapproximability depends on the ratio $(1-\beta)m/k$ and we would want the ratio $(1-\beta)m/k$ to be as large as possible to get better results.

I have not specified details of the problem $\Pi$ and the constants as I don't think they are necessary for improving the results. This will help to keep the question minimal and general enough for others to benefit from.

Attempt 1:

Theorem 16.23 [1]: For any positive constant $\delta >0$, $\text{NP}\subseteq \text{PCP}_{1, 7/8 + \delta} \left(O\left(\log n\right), 3\right)$, and the verifier is restricted to use only functions that check the "or" of three bits or their negations.

For any $\delta >0$ no polynomial-time algorithm can distinguish between MAX E3SAT instances in which all clauses are satisfiable, and instances in which a $7/8 +\delta$ fraction of the clauses are satisfiable, unless P=NP

So using this theorem and the reduction we can deduce a gap-preserving reduction of $\left(1, 1+\frac{c_2(1-\beta)m}{c_1k}\right)$. A simple and conservative bound for $k$ is $2m$, assuming all clauses are distinct, all literals in a clause are distinct, and both $x_i$ and $\neg x_i$ don't occur in the same clause. This then gives the result that an $\alpha$-approximation algorithmn for $\Pi$, with $\alpha < 1+\frac{c_2(1-\beta)}{2c_1}$ and $\beta=7/8$, will imply P=NP.

Attempt 2:

I recently looked into [2]. The $(1016-\epsilon )/1015$ inapproximability result for MAX-(3,2B)-SAT seems to be relevant. The structure of the problem can help in bounding $k$ to $3m/4$ (need to verify calculations), as each literal occurs twice. However, this doesn't seem to lead to a better result due to small $(1-\beta)$.


[1] Williamson, David P.; Shmoys, David B., The design of approximation algorithms, Cambridge: Cambridge University Press (ISBN 978-0-521-19527-0/hbk; 978-1-139-06515-3/ebook). xi, 504 p. (2011). ZBL1219.90004.

[2] Berman, Piotr; Karpinski, Marek; Scott, D. Alexander, Approximation Hardness of Short Symmetric Instances of MAX-3SAT (2004).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.