Eden Chlamtac

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 Õ(m¹/³)-approximation improving on the Õ(m¹/²)-approximation due to Elkin and Peleg (where m is the number of sets). Our approximation algorithm for MMSAt (for circuits of depth t) gives an Õ(N^1−δ) approximation for δ = ¹₃2³−⌈t/2^⌉, where N is the number of gates and variables. No non-trivial approximation algorithms for MMSAt with t ≥ 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 Ω̃(m¹/^4−ε) 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−ε where ε → 0 as the circuit depth t → ∞.