Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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$.
Perhaps this gives you a start on finding the actual approximation ratio of your local search algorithm.
