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
