Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR99-043 | 5th November 1999 00:00

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

TR99-043
Authors: Venkatesan Guruswami
Publication: 15th November 1999 17:31
Keywords:

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

ISSN 1433-8092 | Imprint