Nimrod Megiddo
Journal of Symbolic Computation
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.
Nimrod Megiddo
Journal of Symbolic Computation
Juliann Opitz, Robert D. Allen, et al.
Microlithography 1998
Laxmi Parida, Pier F. Palamara, et al.
BMC Bioinformatics
Guillaume Buthmann, Tomoya Sakai, et al.
ICASSP 2025