W.C. Tang, H. Rosen, et al.
SPIE Optics, Electro-Optics, and Laser Applications in Science and Engineering 1991
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.
W.C. Tang, H. Rosen, et al.
SPIE Optics, Electro-Optics, and Laser Applications in Science and Engineering 1991
Martin Charles Golumbic, Renu C. Laskar
Discrete Applied Mathematics
I.K. Pour, D.J. Krajnovich, et al.
SPIE Optical Materials for High Average Power Lasers 1992
Imran Nasim, Michael E. Henderson
Mathematics