Treffer: Best possible approximation algorithm for MAX SAT with cardinality constraint.
Title:
Best possible approximation algorithm for MAX SAT with cardinality constraint.
Authors:
Source:
Approximation Algorithms for Combinatiorial Optimization. 1998, p193-199. 7p.
Database:
Supplemental Index
Weitere Informationen
In this work we consider the MAX SAT problem with the additional constraint that at most p variables have a true value. We obtain (1 — e−1)-approximation algorithm for this problem. Feige [5] proves that for the MAX SAT with cardinality constraint with clauses without negations this is the best possible performance guarantee unless P=NP. [ABSTRACT FROM AUTHOR]