What is the inapproximability status of Max-One-in-Three SAT for satisfiable instances?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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}$)].
