%AChlamtáč, Eden%AMakarychev, Yury%AVakilian, Ali%AMegow, Nicole Ed.%ASmith, Adam Ed.%D2023%ISchloss Dagstuhl – Leibniz-Zentrum für Informatik
%KRed-Blue Set Cover Problem; Circuit Minimum Monotone Satisfying Assignment (MMSA) Problem; LP Rounding
%MOSTI ID: 10518037
%PMedium: X
%TApproximating Red-Blue Set Cover and Minimum Monotone Satisfying Assignment
%XWe 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^{1/3})-approximation improving on the Õ(m^{1/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 Õ(N^{1-δ}) approximation for δ = 1/3 2^{3-⌈t/2⌉}, where N is the number of gates and variables. No non-trivial approximation algorithms for MMSA_t 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^{1/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 → ∞.
Country unknown/Code not availablehttps://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.11OSTI-MSA