<p>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.</p>

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

CC BY-SA 4.0
2019-02-16T23:06:03.190Z
This is better known as Max 1-in-$k$ Hitting Set (in your case $k=3$) and was studied, for example, here https://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.
Sasho Nikolov
CC BY-SA 4.0
2019-02-22T17:23:34.367Z
Thank you for the reference @SashoNikolov. This answers my question!
karmanaut
<np-hardness><sat><approximation-hardness>
Is monotone 1-in-3 MAXSAT known to be APX hard?
karmanaut
# Is monotone 1-in-3 MAXSAT known to be APX hard?

(Asked by: username_0 on 2019-02-16)

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

**Tags:** np-hardness, sat, approximation-hardness

> **Comments:**
> **username_1**: This is better known as Max 1-in-$k$ Hitting Set (in your case $k=3$) and was studied, for example, here https://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.  
> **username_0**: Thank you for the reference @SashoNikolov. This answers my question!  

---

## 0 answers

