1
$\begingroup$

Assume that in classical Local Search algorithm for MAX-SAT we could flip no more than $r \leq n/2$ variables (let's call it $r$-flip) on every iteration. More precise: on every iteration we're finding $r$-flip which satisfies more clauses then was satisfied before the flip.

What is the approximation ratio of this algorithm? Is there any worst case where my algorithm has multiplicative error 1/2?

$\endgroup$

1 Answer 1

1
$\begingroup$

Suppose that the all-zero assignment is a local optimum for your algorithm, for some CNF $\varphi$, say satisfying an $\alpha$ fraction of the clauses. If we choose any assignment of weight at most $n/2$, it should satisfy at most an $\alpha$ fraction of the clauses. In particular, a random assignment of weight exactly $n/2$ satisfies at most an $\alpha$ fraction of clauses. If we assume that no clauses are empty (empty clauses only work in our favor), then every clause is satisfied with probability at least $1/2$ under this distribution. Hence $\alpha \geq 1/2$, and so your algorithm gives a $1/2$ approximation.

If $\alpha = 1/2$ then all clauses are unit clauses. Since the all-zero assignment is a local optimum, this means that for each variable $x_i$, there must be at least as many clauses $\bar{x}_i$ than clauses $x_i$. Hence the all-zero assignment is actually optimal. This shows that there is no worst case in which the approximation ratio is exactly $1/2$.

Perhaps this gives you a start on finding the actual approximation ratio of your local search algorithm.

$\endgroup$
5
  • $\begingroup$ thanks for your answer, but if we say that $r < n/2$ (strictly), then will there be an assigment with approximation ratio exatly 1/2 ? For example if $n$ is odd and $r \leq n/2 \Rightarrow r < n /2$ so we couldn't take a random assignment of weight $n / 2$ $\endgroup$
    – envy grunt
    Commented Feb 6, 2022 at 11:55
  • $\begingroup$ If you change the question, the answer might change. I've given you some hints on how to approach the question, you take it from here. $\endgroup$ Commented Feb 6, 2022 at 13:44
  • $\begingroup$ I would like to know something about the worst-case in this algorithm, my bad that I set $r \leq n / 2$, it should be $r < n / 2$ to generalize this algorithm for arbitary n. Can I build the worst case from your answer, or better edit the questing / ask a new one? $\endgroup$
    – envy grunt
    Commented Feb 6, 2022 at 14:35
  • $\begingroup$ Also, why $\alpha = 1/2$ impies that all clauses are unit clauses? Here is the example for $r = 1$ and $n =3$, where ratio is exact $1/2$. $\varphi = x_1 \vee (\neg x_1 \wedge x_2 \wedge x_3)$, and $(0, 0, 0)$ is a local optimum for $r = 1$ with approximation ratio $1/2$ $\endgroup$
    – envy grunt
    Commented Feb 6, 2022 at 16:30
  • 1
    $\begingroup$ Any clause which is not a unit clause is satisfied with probability more than $1/2$ (unless $n$ is very small), which is why $\alpha = 1/2$ is only possible when you have only unit clauses. $\endgroup$ Commented Feb 6, 2022 at 17:49

Your Answer

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

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