Charles A Micchelli
Journal of Approximation Theory
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.
Charles A Micchelli
Journal of Approximation Theory
Ligang Lu, Jack L. Kouloheris
IS&T/SPIE Electronic Imaging 2002
R.A. Brualdi, A.J. Hoffman
Linear Algebra and Its Applications
Trang H. Tran, Lam Nguyen, et al.
INFORMS 2022