What is the best-known inapproximability result for MIN-3CNF-DELETION?

Question

I am really curious what the best-known inapproximability result is for MIN-3CNF-DELETION. To clarify, this is the problem of minimizing the number of unsatisfied clauses in a CNF SAT formula with at most 3 literals per clause. The objective function is the number of unsatisfied clauses. The strongest hardness result I have been able to find is that of MIN-HORN-DELETION, which is a restricted variant of MIN-3CNF-DELETION. As far as I know the best-known inapproximability result for MIN-HORN-DELETION is that which is given in The Approximability of Constraint Satisfaction Problems by Khanna et al (2000).

However, I have not yet been able to find explicit references to MIN-3CNF-DELETION. Is it even harder than MIN-HORN-DELETION? In which case, what is the best known inapproximability threshhold? Any feedback would be most welcome. Thanks!

Answer 1

There is no approximation algorithm for MIN-3CNF-DELETION at all since it is not even possible to determine in polynomial time whether a 3 CNF SAT instance is satisfiable or not (if P≠NP). That is, it is not possible to determine if the objective function is equal to 0 or strictly positive. Specifically, if we had an $f(n)$ approximation algorithm for the problem, given a satisfiable instance the algorithm would find a solution of cost $0 \cdot f(n) = 0$ ; that is, a solution that satisfies the instance.

In contrast, if an instance of Min-Horn-Deletion or Min-2CNF-Deletion is (completely) satisfiable, we can efficiently find a solution that satisfies all clauses. Thus it makes sense to talk about approximation algorithms for Min-Horn-Deletion and Min-2CNF-Deletion.

Answer 2

The problem MIN-3CNF-DELETION you refer to is better known as MAX-3CNF-SAT (or simply MAX-3SAT for short). Presented as a decision problem, it's the problem of determining (for any input value m) whether there exists an assignment which satisfies at least m of the CNF clauses; presented as an optimization problem, it's the problem of determining the maximum number of clauses which any assignment may satisfy.

This presentation as an optimization problem is clearly complementary to the problem you describe, and (unlike MIN-3CNF-DELETION), it makes sense to consider the feasibility of approximation versions of the problem with multiplicative error because the most extreme value isn't zero. In fact, MAX-3-SAT cannot be approximated to within a constant factor better than 7/8 (unless P = NP). Furthermore, Karloff and Zwick demonstrated that there does exist an approximation algorithm achieving that upper bound.

Edited to add. The business with the approximation factor in Karloff and Zwick's result seems to be somewhat more complicated than it appears. Many papers in the literature describe their result simply as a 7/8-approximation algorithm. However, Zwick himself writes the following in a footnote on page 1 of this paper:

More precisely, [KZ97] obtain a $(7/8 - \epsilon)$-approximation algorithm for satisfiable instances of MAX-3SAT and provide compelling analytical and numerical evidence that suggest that the performance ratio of the algorithm is $7/8-\epsilon$ for all instances of the problem, for every $\epsilon > 0$. It is possible to show that the $\epsilon$ in the above expressions can be eliminated.