Loading...
Please wait, while we are loading the content...
Inapproximability results for set splitting and satisfiability problems with no mixed clauses (2000).
| Content Provider | CiteSeerX |
|---|---|
| Author | Guruswami, Venkatesan |
| Abstract | We prove hardness results for approximating set splitting problems and also instances of satisfiability problems which have no "mixed" clauses, i.e every clause has either all its literals unnegated or all of them negated. Results of Håstad [8] imply tight hardness results for set splitting when all sets have size exactly k 4 elements and also for non-mixed satisfiability problems with exactly k literals in each clause for k 4. We consider the case k = 3. For the Max E3-Set Splitting problem in which all sets have size exactly 3, we prove a hardness result for approximating within any factor better than 21/22. We also 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 [7]. We give a PCP construction which is a variant of the one in [7] 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 t... |
| File Format | |
| Publisher Date | 2000-01-01 |
| Access Restriction | Open |
| Subject Keyword | Hardness Result Set Splitting Satisfiability Problem Inapproximability Result Mixed Clause Satisfiable Instance Pcp Construction Max E3-set Splitting Recent Pcp Construction Max E3-set Splitting Problem Non-mixed Satisfiability Problem Non-mixed Max Set Splitting Problem Latter Result |
| Content Type | Text |
