文章基本信息

标题：MAX NP-Completeness Made Easy
本地全文：下载
作者：Pierluigi Crescenzi ; Luca Trevisan
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1997
卷号：1997
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We introduce a simple technique to obtain reductions between optimization constraint satisfaction problems. The technique uses the probabilistic method to reduce the size of disjunctions. As a first application, we prove the MAX NP-completeness of MAX 3SAT without using the PCP theorem (thus solving an open question posed in Khanna et al. (1994)). Successively, we show that the ``planar'' restrictions of several optimization constraint satisfaction problems admit linear-time approximation schemes (thus improving the results of Khanna and Motwani (1996)).
关键词：Approximation-Preserving Reductions, MAX NP, Maximum Planar Satisfiability, Probabilistic Method