4
$\begingroup$

In MAX-SAT, we are given a formula and want to maximize the number of satisfied clauses. I.e., 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, we are given two different formulas and want to find an assignment that maximizes the smaller number of satisfied clauses. I.e., given two formulas $\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, we want to find the largest $k\in\{1,\ldots,n\}$ 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 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.

Has this problem been studied? It is obviously NP-hard; what is known about approximations?

EDIT: 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?

$\endgroup$

closed as off-topic by D.W. Jan 11 at 6:49

  • This question does not appear to be about computer science within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Nov 21 '18 at 16:30
  • $\begingroup$ Cross-posted: cs.stackexchange.com/q/100375/755, cstheory.stackexchange.com/q/42177/5038. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. If you post on the wrong site, please delete the first copy before posting it on another site. Thank you! $\endgroup$ – D.W. Jan 11 at 6:49
  • $\begingroup$ I'm voting to close this question because it was cross-posted. $\endgroup$ – D.W. Jan 11 at 6:49
  • $\begingroup$ @D.W. Note that I cross-posted it only after about 6 weeks that it appeared here without reply. $\endgroup$ – Erel Segal-Halevi Jan 11 at 6:56
  • $\begingroup$ @ErelSegal-Halevi, yes, I saw that. $\endgroup$ – D.W. Jan 11 at 8:14