4
$\begingroup$

Monotone 1-in-3 SAT is the problem where each clause of the SAT problem contains exactly 3 positive variables. The goal is to find an assignment such that exactly one variable is true in each clause and maximizes the number of clauses satisfied.

Is this problem APX hard? More importantly, is there a reference I can cite (or the result is folklore)?

$\endgroup$
  • 3
    $\begingroup$ This is better known as Max 1-in-$k$ Hitting Set (in your case $k=3$) and was studied, for example, here people.eecs.berkeley.edu/~luca/pubs/gt05.pdf. Most papers seem to focus on large $k$, but I believe that the problem should be APX-hard to $k=3$ as well. $\endgroup$ – Sasho Nikolov Feb 16 at 23:06
  • $\begingroup$ Thank you for the reference @SashoNikolov. This answers my question! $\endgroup$ – karmanaut Feb 22 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.