Abstract.
We study the approximability of the Maximum Satisfiability Problem (MAX SAT) and of the boolean k -ary Constraint Satisfaction Problem (MAX k CSP) restricted to satisfiable instances. For both problems we improve on the performance ratios of known algorithms for the unrestricted case.
Our approximation for satisfiable MAX 3CSP instances is better than any possible approximation for the unrestricted version of the problem (unless P=NP). This result implies that the requirement of perfect completeness weakens the acceptance power of non-adaptive PCP verifiers that read 3 bits.
We also present the first non-trivial results about PCP classes defined in terms of free bits that collapse to P.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received August 1997; revised February 1999.
Rights and permissions
About this article
Cite this article
Trevisan, L. Approximating Satisfiable Satisfiability Problems . Algorithmica 28, 145–172 (2000). https://doi.org/10.1007/s004530010035
Issue Date:
DOI: https://doi.org/10.1007/s004530010035