<p>The most relevant paper I know is </p>

<p>"The Complexity of Making Unique Choices: Approximating 1-in-k SAT" by Guruswami and Trevisan <a href="http://theory.stanford.edu/~trevisan/pubs/gt05.pdf">(link)</a></p>

<p>They give an algorithm for satisfiable instances which for $k=3$ would achieve a ratio of $\frac{4}{9}$, beating the random assignment. They also mention that 1-in-3 SAT is $\frac{5}{6}$-inapproximable, but I'm not sure if that applies to satisfiable instances. They cite Guruswami's Master's thesis for this.</p>

CC BY-SA 3.0
2012-12-05T18:19:44.553Z
2012-12-05T18:19:44.553Z
Michael Lampis
<p>The best algorithm I am aware of is the algorithm by Zwick, which gives $3/4$ approximation for satisfiable instances. It is presented in    </p>

<blockquote>
  <p>Uri Zwick. “Approximation Algorithms for Constraint Satisfaction Problems Involving at Most Three Variables per Constraint.” In Proc. of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, 1997.</p>
</blockquote>

<p>I don't know if this is the best currently known algorithm. This paper also describes an algorithm that gives 5/8 approximation for satisfiable instances of every Boolean 3-CSP. This result is known to be optimal [O'Donnell, Wu '09 (assuming Khot's $d$-to-$1$ conjecture), Håstad '12 (assuming $\mathrm{P\neq NP}$)].</p>

CC BY-SA 3.0
2012-12-07T05:09:45.030Z
2012-12-07T16:34:24.197Z
2012-12-07T16:34:24.197Z
Yury
<p>What is the inapproximability status of Max-One-in-Three SAT for satisfiable instances?</p>

<sat><approximation-hardness>
Inappoximability status of Max One in Three SAT for satisfiable instances
vikku
# Inappoximability status of Max One in Three SAT for satisfiable instances

(Asked by: username_0 on 2012-12-04)

What is the inapproximability status of Max-One-in-Three SAT for satisfiable instances?

**Tags:** sat, approximation-hardness


---

## 2 answers

### Answer by username_1 on 2012-12-05. Score: 12

The most relevant paper I know is

"The Complexity of Making Unique Choices: Approximating 1-in-k SAT" by Guruswami and Trevisan [(link)](http://theory.stanford.edu/~trevisan/pubs/gt05.pdf)

They give an algorithm for satisfiable instances which for $k=3$ would achieve a ratio of $\frac{4}{9}$, beating the random assignment. They also mention that 1-in-3 SAT is $\frac{5}{6}$-inapproximable, but I'm not sure if that applies to satisfiable instances. They cite Guruswami's Master's thesis for this.


---

### Answer by username_2 on 2012-12-07. Score: 9

The best algorithm I am aware of is the algorithm by Zwick, which gives $3/4$ approximation for satisfiable instances. It is presented in

> Uri Zwick. “Approximation Algorithms for Constraint Satisfaction Problems Involving at Most Three Variables per Constraint.” In Proc. of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, 1997.

I don't know if this is the best currently known algorithm. This paper also describes an algorithm that gives 5/8 approximation for satisfiable instances of every Boolean 3-CSP. This result is known to be optimal [O'Donnell, Wu '09 (assuming Khot's $d$-to-$1$ conjecture), Håstad '12 (assuming $\mathrm{P\neq NP}$)].


---

