Shashanka Ubaru, Lior Horesh, et al.
Journal of Biomedical Informatics
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.
Shashanka Ubaru, Lior Horesh, et al.
Journal of Biomedical Informatics
Jianke Yang, Robin Walters, et al.
ICML 2023
Richard M. Karp, Raymond E. Miller
Journal of Computer and System Sciences
Robert Manson Sawko, Malgorzata Zimon
SIAM/ASA JUQ