Given a set \(X\)  of \(n\)  variables and a set \(C\)  of \(m\)  clauses,
where each variable has exactly 3 literals
(in 3 different clauses)
and each clause is the disjunction of exactly 2 literals
(of 2 different variables),
E3-Occ-Max-E2-SAT is the problem of finding an assignment of \(X\)  that satisfies
the maximum number of clauses in \(C\) .
The problem E3-Occ-Max-E2-SAT is known to be APX-hard even if
the 3 literals of each variable are neither all positive nor all negative;
see for example the gap-preserving reduction from
Max-Cut in cubic graphs to this problem
in the DIMACS version of [1]}.
As a result, we can assume that each variable has
either 2 positive and 1 negative literals,
or 1 positive and 2 negative literals.
