Fernando Martinez, Tao Li, et al.
ICLR 2026
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.
Fernando Martinez, Tao Li, et al.
ICLR 2026
Frank R. Libsch, Takatoshi Tsujimura
Active Matrix Liquid Crystal Displays Technology and Applications 1997
Joy Y. Cheng, Daniel P. Sanders, et al.
SPIE Advanced Lithography 2008
R.A. Brualdi, A.J. Hoffman
Linear Algebra and Its Applications