In MAX-SAT, given a formula, we want to maximize the number of satisfied clauses: given a formula $\phi = c_1 \cap \cdots \cap c_n$, where each $c_i$ is a disjunction, we want to find the largest $k\in\{1,\ldots,n\}$ such that, for some assignment, some $k$ clauses $c_{i1},\ldots,c_{ik}$ are true.

In MAX-MIN-SAT, given two different formulas, we want to maximize the minimum number of satisfied clauses in both. I.e., given $\phi_a = a_1 \cap \cdots \cap a_n$ and $\phi_b = b_1 \cap \cdots \cap b_n$, where each $a_i$ and each $b_i$ is a disjunction, find the largest $k$ such that, for some assignment, some $k$ clauses $a_{i1},\ldots,a_{ik}$ and some $k$ clauses $b_{j1},\ldots,b_{jk}$ are true.

To illustrate the difference between the problems, suppose we have two assignments: one assignment satisfies 10 clauses in $\phi_a$ and 1 clause in $\phi_b$, while another assignment satisfies 5 clauses in $\phi_a$ and 4 clauses in $\phi_b$. Then, MAX-SAT (on $\phi_a \cap \phi_b$) would prefer the first assignment since it satisfies $11>9$ clauses overall, while MAX-MIN-SAT would prefer the second assignment since it satisfies at least $4>1$ clauses in both formulas.

This problem is obviously NP-hard, so I am looking for reasonable approximations.

As a first approximation, suppose each formula is a conjunction of $n$ clauses, and each clause is a disjunction of $l$ variables. Suppose we set each variable randomly. Then, each clause is unsatisfied with probability $2^{-l}$. So the expected number of unsatisfied clauses in each formula is $2^{-l}n$. So the expected number of unsatisfied clauses in both formulas is $2^{1-l}n$. So there exists an assignment in which the total number of unsatisfied clauses is at most $2^{1-l}n$. In that assignment, in each formula, at least $(1-2^{1-l})n$ clauses are satisfied. So we have a constant-factor $(1-2^{1-l})$ approximation to MAX MIN SAT.

Is there a better approximation?

Posted some weeks ago in cs.SE, with no replies


1 Answer 1


Some such problems are considered here https://eccc.weizmann.ac.il/report/2014/098/ under the name "simultaneous approximation".

See Theorems 1.1 and 1.3.

  • $\begingroup$ This looks like exactly the problem I am interested in. Thanks! $\endgroup$ Commented Jan 11, 2019 at 5:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.