Best Possible Approximation Algorithm for MAX SAT with Cardinality Constraint

0.00 Avg rating—0 Votes

Article ID:	iaor20121044
Volume:	30
Issue:	3
Start Page Number:	398
End Page Number:	405
Publication Date:	Jan 2001
Journal:	Algorithmica
Authors:	Sviridenko M I
Keywords:	approximation, boolean programming, NP-hard

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= P .

Reviews

Required fields are marked *. Your email address will not be published.