Simeon Furrer, Dirk Dahlhaus
ISIT 2005
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.
Simeon Furrer, Dirk Dahlhaus
ISIT 2005
M. Shub, B. Weiss
Ergodic Theory and Dynamical Systems
Igor Devetak, Andreas Winter
ISIT 2003
W.F. Cody, H.M. Gladney, et al.
SPIE Medical Imaging 1994