MaxSAT (Boolean Satisfiability)
Jump to navigation
Jump to search
Description
Given an instance of SAT represented in Conjunctive Normal Form (CNF), compute an assignment to the variables that maximizes the number of satisfied clauses.
Related Problems
Generalizations: Conjunctive Normal Form SAT
Related: SAT, Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, Not-All-Equal 3-SAT (NAE 3SAT), Monotone Not-All-Equal 3-SAT (Monotone NAE 3SAT), k-SAT, 2SAT, 3SAT, 3SAT-5, 4SAT, Monotone 3SAT, XOR-SAT, Horn SAT, Dual-Horn SAT, Renamable Horn
Parameters
$n$: number of variables
Table of Algorithms
Currently no algorithms in our database for the given problem.
Reductions TO Problem
| Problem | Implication | Year | Citation | Reduction |
|---|---|---|---|---|
| st-Maximum Flow | assume: SETH then: for any fixed constants $\epsilon > {0}$, $c_1,c_2 \in ({0},{1})$, on graphs with $n$ nodes $|S|=\tilde{\Theta}(n^{c_1})$, $|T|=\tilde{\Theta(n^{c_2})}$, $m=O(n)$ edges, and capacaties in $\{1,\cdots,n\}$, target cannot be solved in $O((|S|T|m)^{1-\epsilon})$ |
2018 | https://dl-acm-org.ezproxy.canberra.edu.au/doi/abs/10.1145/3212510 | link |
| All-Pairs Maximum Flow | assume: SETH then: for any fixed $\epsilon > {0}$, in graphs with $n$ nodes, $m=O(n)$ edges, and capacities in $\{1,\cdots,n\}$ target cannot be solved in time $O((n^{2}m)^{1-\epsilon})$ |
2018 | https://dl-acm-org.ezproxy.canberra.edu.au/doi/abs/10.1145/3212510 | link |
| All-Pairs Maximum Flow | assume: SETH then: for any fixed constants $\epsilon > {0}$, $c_1,c_2 \in ({0},{1})$, on graphs with $n$ nodes $|S|=\tilde{\Theta}(n^{c_1})$, $|T|=\tilde{\Theta(n^{c_2})}$, $m=O(n)$ edges, and capacaties in $\{1,\cdots,n\}$, target cannot be solved in $O((|S|T|m)^{1-\epsilon})$ |
2018 | https://dl-acm-org.ezproxy.canberra.edu.au/doi/abs/10.1145/3212510 | link |
| st-Maximum Flow | assume: SETH then: for any fixed $\epsilon > {0}$, in graphs with $n$ nodes, $m=O(n)$ edges, and capacities in $\{1,\cdots,n\}$ target cannot be solved in time $O((n^{2}m)^{1-\epsilon})$ |
2018 | https://dl-acm-org.ezproxy.canberra.edu.au/doi/abs/10.1145/3212510 | link |
| Maximum Local Edge Connectivity | assume: SETH then: for any $\epsilon > {0}$, in graphs with $n$ nodes and $\tilde{O}(n)$ edges, target cannot be solved in time $O(n^{2-\epsilon})$ |
2018 | https://dl-acm-org.ezproxy.canberra.edu.au/doi/abs/10.1145/3212510 | link |