Best Possible Approximation Algorithm for MAX SAT with Cardinality Constraint

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 . Received August 20, 1998; revised June 23, 1999, and April 17, 2000.