Martin Charles Golumbic, Renu C. Laskar
Discrete Applied Mathematics
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.
Martin Charles Golumbic, Renu C. Laskar
Discrete Applied Mathematics
David W. Jacobs, Daphna Weinshall, et al.
IEEE Transactions on Pattern Analysis and Machine Intelligence
Elizabeth A. Sholler, Frederick M. Meyer, et al.
SPIE AeroSense 1997
John S. Lew
Mathematical Biosciences