Take the 2-minute tour ×
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.

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

share|improve this question
add comment

2 Answers

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.