Abstract.
We consider the MAX SAT problem with the additional constraint that at most P variables have a true value. We obtain a (1-e -1 ) -approximation algorithm for this problem. Feige [6] has proved that for MAX SAT with cardinality constraint with clauses without negations this is the best possible performance guarantee unless P=\NP .
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received August 20, 1998; revised June 23, 1999, and April 17, 2000.
Rights and permissions
About this article
Cite this article
Sviridenko, M. Best Possible Approximation Algorithm for MAX SAT with Cardinality Constraint. Algorithmica 30, 398–405 (2001). https://doi.org/10.1007/s00453-001-0019-5
Issue Date:
DOI: https://doi.org/10.1007/s00453-001-0019-5