# Hardness of approximation by reduction from MAX-E3SAT

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)$$.

References:

[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).