Approximating Red-Blue Set Cover and Minimum Monotone Satisfying Assignment

We provide new approximation algorithms for the Red-Blue Set Cover and Circuit Minimum Monotone Satisfying Assignment (MMSA) problems. Our algorithm for Red-Blue Set Cover achieves $\tilde{O}(m^{1\mathrm{/}3})$-approximation improving on the $\tilde{O}(m^{1\mathrm{/}2})$-approximation due to Elkin and Peleg (where $m$ is the number of sets). Our approximation algorithm for MMSA${}_t$ (for circuits of depth $t$) gives an $\tilde{O}(N^{1-\delta })$ approximation for $\delta =\frac{1}{3}{2}^{3-\lceil t\mathrm{/}2\rceil }$, where $N$ is the number of gates and variables. No non-trivial approximation algorithms for MMSA${}_t$ with $t\ge 4$ were previously known. We complement these results with lower bounds for these problems: For Red-Blue Set Cover, we provide a nearly approximation preserving reduction from Min $k$-Union that gives an $\tilde{\mathrm{\Omega }}(m^{1\mathrm{/}4-\epsilon })$ hardness under the Dense-vs-Random conjecture, while for MMSA we sketch a proof that an SDP relaxation strengthened by Sherali–Adams has an integrality gap of $N^{1-\epsilon }$ where $\epsilon \to 0$ as the circuit depth $t\to \mathrm{\infty }$.