Laxmi Parida, Pier F. Palamara, et al.
BMC Bioinformatics
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.
Laxmi Parida, Pier F. Palamara, et al.
BMC Bioinformatics
David W. Jacobs, Daphna Weinshall, et al.
IEEE Transactions on Pattern Analysis and Machine Intelligence
Ziv Bar-Yossef, T.S. Jayram, et al.
Journal of Computer and System Sciences
T. Graham, A. Afzali, et al.
Microlithography 2000