<p>Some such problems are considered here 
<a href="https://eccc.weizmann.ac.il/report/2014/098/" rel="nofollow noreferrer">https://eccc.weizmann.ac.il/report/2014/098/</a>
under the name "simultaneous approximation".</p>

<p>See Theorems 1.1 and 1.3.</p>

CC BY-SA 4.0
2019-01-11T05:39:28.277Z
This looks like exactly the problem I am interested in. Thanks!
Erel Segal-Halevi
CC BY-SA 4.0
2019-01-09T20:43:43.800Z
2019-01-09T20:43:43.800Z
james
<p>In <a href="https://en.wikipedia.org/wiki/Maximum_satisfiability_problem" rel="nofollow noreferrer">MAX-SAT</a>, given a formula, we want to maximize the number of satisfied clauses: given a formula <span class="math-container">$\phi = c_1 \cap \cdots \cap c_n$</span>, where each <span class="math-container">$c_i$</span> is a disjunction, we want to find the largest <span class="math-container">$k\in\{1,\ldots,n\}$</span> such that, for some assignment, some <span class="math-container">$k$</span> clauses <span class="math-container">$c_{i1},\ldots,c_{ik}$</span> are true.</p>

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

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

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

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

<p>Is there a better approximation? </p>

<p><sub><a href="https://cs.stackexchange.com/q/100375/1342">Posted some weeks ago in cs.SE,</a> with no replies</sub></p>

<approximation-algorithms><optimization><sat>
Maximum-minimum satisfiability
Erel Segal-Halevi
# Maximum-minimum satisfiability

(Asked by: username_0 on 2019-01-09)

In [MAX-SAT](https://en.wikipedia.org/wiki/Maximum_satisfiability_problem), 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,](https://cs.stackexchange.com/q/100375/1342) with no replies

**Tags:** approximation-algorithms, optimization, sat

---

## 1 answers

### Answer by username_1 on 2019-01-09. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: This looks like exactly the problem I am interested in. Thanks!  

---

