Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question

The most relevant paper I know is

"The Complexity of Making Unique Choices: Approximating 1-in-k SAT" by Guruswami and Trevisan (link)

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.

share|cite|improve this answer

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}$)].

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.