Questions tagged [maxsat]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
25 views

Why do exact MaxSAT algorithms scale exponentially as a function of the number of clauses?

As stated in this recent paper from ijcai https://www.ijcai.org/Proceedings/2019/0166.pdf The top -Exact- algorithms worst case complexities are stated as follows where m is the number of clauses in ...
3
votes
1answer
42 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 ...
2
votes
1answer
116 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 ...
2
votes
1answer
109 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 \...