Arnon Amir, Michael Lindenbaum
IEEE Transactions on Pattern Analysis and Machine Intelligence
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.
Arnon Amir, Michael Lindenbaum
IEEE Transactions on Pattern Analysis and Machine Intelligence
Guo-Jun Qi, Charu Aggarwal, et al.
IEEE TPAMI
W.F. Cody, H.M. Gladney, et al.
SPIE Medical Imaging 1994
Charles A Micchelli
Journal of Approximation Theory