Juliann Opitz, Robert D. Allen, et al.
Microlithography 1998
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.
Juliann Opitz, Robert D. Allen, et al.
Microlithography 1998
Imran Nasim, Melanie Weber
SCML 2024
M.V. Menon
Technometrics
R.A. Toupin
Archive for Rational Mechanics and Analysis