ECCC-Report TR99-043https://eccc.weizmann.ac.il/report/1999/043Comments and Revisions published for TR99-043en-usMon, 15 Nov 1999 17:31:57 +0200
Paper TR99-043
| The Approximability of Set Splitting Problems and Satisfiability Problems with no Mixed Clauses |
Venkatesan Guruswami
https://eccc.weizmann.ac.il/report/1999/043
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).
Mon, 15 Nov 1999 17:31:57 +0200https://eccc.weizmann.ac.il/report/1999/043