Zhihua Xiong, Yixin Xu, et al.
International Journal of Modelling, Identification and Control
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.
Zhihua Xiong, Yixin Xu, et al.
International Journal of Modelling, Identification and Control
John S. Lew
Mathematical Biosciences
Ruixiong Tian, Zhe Xiang, et al.
Qinghua Daxue Xuebao/Journal of Tsinghua University
Jonathan Ashley, Brian Marcus, et al.
Ergodic Theory and Dynamical Systems