# Questions tagged [maxsat]

The tag has no usage guidance.

7 questions
Filter by
Sorted by
Tagged with
44 views

### Is MAX-averageSAT a well-known problem?

Is there any variant of the Boolean SAT or Max-SAT problem that has a flavor of maximizing or minimizing the average of the weights of the satisfied clauses of a WCNF formula? Any literature on an ...
426 views

### MAX 2-SAT is polynomial time reducible to 2-SAT?

I know that 2-SAT is solvable in polynomial time and 2-SAT is NP-Hard. I have issue about this statement: MAX 2-SAT is polynomial-time reducible to 2-SAT. Can you explain to me how reduction looks ...
233 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 \...
• 933
1 vote
204 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 ...
• 37
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 ...
• 158
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 ...