Salvatore Certo, Anh Pham, et al.
Quantum Machine Intelligence
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.
Salvatore Certo, Anh Pham, et al.
Quantum Machine Intelligence
Hannaneh Hajishirzi, Julia Hockenmaier, et al.
UAI 2011
Tong Zhang, G.H. Golub, et al.
Linear Algebra and Its Applications
R.A. Brualdi, A.J. Hoffman
Linear Algebra and Its Applications