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$

Your Answer

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

Browse other questions tagged or ask your own question.