# Maximum-minimum satisfiability

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