# Questions tagged [maxsat]

The tag has no usage guidance.

7 questions
Filter by
Sorted by
Tagged with
61 views

### Could someone give me an example of MaxSat's approximable 1/2 algorithm?

in my Complexity class I have to present the 1/2 MaxSat approximation algorithm that appears in the Vazirani, Vijay V - Approximation algorithms-Spring (2011) [Image attached]. The problem is that it ...
158 views

### MAX-SAT approximation factor

I am stuck on an exercise that ask the approximation factor of a MAX-SAT approximated algorithm generalized from a MAX-3SAT algorithm MAX-3SAT: set every variable with a random value ($0$ or $1$ each ...
1 vote
201 views

### MAX-SAT 2-Approximation algorithm

I have the two following questions: I know SAT -> MAX-SAT but how can I show that if MAX-SAT is solved in polynomial time then SAT is solved in polynomial time as well?(I guess using approximation ...
1 vote
31 views

### 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 ...
228 views

### Encoding set of At-Most-One constraints as a MAX-SAT problem

Assume a set of variable $V$ = $\{v_1,...,v_m\}$. Given total $n$ at-most-one (AMO) constraints (at most one element in a given set is true) set [of the below form], over the variable set $V$,  AMO \...