Questions tagged [maxsat]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
90 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 ...
Marcus34's user avatar
1 vote
1 answer
175 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 ...
kostger's user avatar
  • 37
0 votes
1 answer
49 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 ...
Diego Dozal Magnani's user avatar
1 vote
1 answer
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 ...
envy grunt's user avatar
3 votes
1 answer
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 ...
Akhil Dixit's user avatar
2 votes
1 answer
370 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 ...
Martin Inf1n1ty's user avatar
2 votes
1 answer
209 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 \...
Pushpa's user avatar
  • 933