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)?

  • 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$ Feb 16, 2019 at 23:06
  • $\begingroup$ Thank you for the reference @SashoNikolov. This answers my question! $\endgroup$
    – karmanaut
    Feb 22, 2019 at 17:23


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.