Sonia Cafieri, Jon Lee, et al.
Journal of Global Optimization
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.
Sonia Cafieri, Jon Lee, et al.
Journal of Global Optimization
Naga Ayachitula, Melissa Buco, et al.
SCC 2007
Hang-Yip Liu, Steffen Schulze, et al.
Proceedings of SPIE - The International Society for Optical Engineering
Fernando Martinez, Tao Li, et al.
ICLR 2026