2
$\begingroup$

Max 1-in-kSAT is the following maximisation problem :

Given $n$ variables $x_1,\dots,x_n$, and $m$ clauses $C_1, \dots, C_m$, find a valuation such that the number of clauses satisfied by exactly one literal is maximal.

In the following paper, there are several inaproximability results about this problem, such as

Theorem 9 : if $ZPP\neq NP$, then for every $\epsilon$, there is a constant $c$ such that there is no polynomial time $(n^{1-\epsilon})$-approximation algorithm for Max 1-in-$(c\log n)$SAT

https://people.eecs.berkeley.edu/~luca/pubs/gt05.pdf

I want to know if this result is still true if we suppose that $m=O(n^{\delta})$ where $\delta$ is any positive constant

Any ideas, remarks, or paper would be useful :)

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.