7
$\begingroup$

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

$\endgroup$
12
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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