On the Approximability of Boolean Max-$k$-CSP

Ainesh Bakshi

Consider the problem of maximizing the number of satisfied constraints of an arbitrary boolean constraint satisfaction problem with arity $k$. We obtain a polynomial time algorithm…