__
TR99-043 | 5th November 1999 00:00
__

#### The Approximability of Set Splitting Problems and Satisfiability Problems with no Mixed Clauses

**Abstract:**

We prove hardness results for approximating set splitting problems and

also instances of satisfiability problems which have no ``mixed'' clauses,

i.e all clauses have either all their literals unnegated or all of them

negated. Recent results of Hastad imply tight hardness results for set

splitting when all sets have size exactly $k \ge 4$ elements and also for

non-mixed satisfiability problems with exactly $k$ literals in each clause

for $k \ge 4$. We consider the problem Max E3-Set Splitting in which sets

have size exactly 3, and prove, by constructing simple gadgets from

3-parity constraints, that Max E3-Set Splitting is hard to approximate

within any factor strictly better than 21/22. We prove that even

satisfiable instances of Max E3-Set Splitting are NP-hard to approximate

better than 27/28; this latter result uses a recent PCP construction of

\cite{GLST98}. We also give a PCP construction which is a variant of the

one in \cite{GLST98} and use it to prove a hardness result of

$11/12+\epsilon$ for approximating non-mixed Max 3Sat, and also a hardness

of $15/16+\epsilon$ for the version where each clause has exactly three

literals (as opposed to up to three literals).