# Radius Local Search Algortihm for Max-Sat problem approximating ratio

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?

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$$.
• 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$ Feb 6, 2022 at 11:55
• 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? Feb 6, 2022 at 14:35
• 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$ Feb 6, 2022 at 16:30
• 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. Feb 6, 2022 at 17:49