Martin C. Gutzwiller
Physica D: Nonlinear Phenomena
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.
Martin C. Gutzwiller
Physica D: Nonlinear Phenomena
Martin Charles Golumbic, Renu C. Laskar
Discrete Applied Mathematics
Yi Zhou, Parikshit Ram, et al.
ICLR 2023
Kenneth L. Clarkson, K. Georg Hampel, et al.
VTC Spring 2007