R.B. Morris, Y. Tsuji, et al.
International Journal for Numerical Methods in Engineering
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.
R.B. Morris, Y. Tsuji, et al.
International Journal for Numerical Methods in Engineering
Imran Nasim, Michael E. Henderson
Mathematics
A. Skumanich
SPIE OE/LASE 1992
Y.Y. Li, K.S. Leung, et al.
J Combin Optim