Loading...
Please wait, while we are loading the content...
Similar Documents
Revisiting the hardness of approximation of Maximum 3-Satisfiability
| Content Provider | Semantic Scholar |
|---|---|
| Author | Finkelstein, Jeffrey |
| Copyright Year | 2014 |
| Abstract | In this work, we attempt to clarify the existing proofs that Maximum 3Satisfiability is both hard to approximate in polynomial time and complete for the class APX under an appropriate type of reduction. By doing this, we hope to provide not only a better understanding of the original proofs, but also a platform on which to base similar proofs. We use this platform to provide a clarification of the existing proofs that Maximum 3-Satisfiability is both hard to approximate by efficient and highly parallel algorithms and complete for the class NCX under an appropriate type of reduction. We introduce the necessary definitions and basic facts in section 2. In subsection 3.1, we present a proof that Maximum 3-Satisfiability is hard to approximate in polynomial time within a constant factor, for sufficiently small constants. The proof here is a careful rewrite of the proofs given in [3, Theorem 6.3] and [9, Corollary 29.8]. The corresponding proof for highly parallel algorithms is in subsection 3.2. In subsection 4.1 we present a proof that Maximum 3-Satisfiability is complete for the class of polynomial time constant factor approximable optimization problems, under an appropriate type of reduction. The proof here is a careful rewrite of the proof given in [3, Theorem 8.6]. The corresponding proof for highly parallel algorithms is in subsection 4.2. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://cs-people.bu.edu/jeffreyf/static/pdf/apxcompleteness.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
