2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

New contributor
james is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
  • $\begingroup$ This looks like exactly the problem I am interested in. Thanks! $\endgroup$ – Erel Segal-Halevi Jan 11 at 5:39

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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