On MAX–SAT with Cardinality Constraint

We consider the weighted MAX–SAT problem with an additional constraint that at most k variables can be set to true. We call this problem k –WMAX–SAT. This problem admits a \((1 - \frac{1}{e})\) -factor approximation algorithm in polynomial time [Sviridenko, Algorithmica 2001] and it is proved that there is no \((1-\frac{1}{e} + \epsilon )\) -factor approximation algorithm in \(f(k)\cdot n^{o(k)}\) time for Maximum Coverage, the unweighted monotone version of k –WMAX–SAT [Manurangsi, SODA 2020]. Therefore, we study two restricted versions of the problem in the realm of parameterized complexity.