2026-07-22T22:30:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18836 2024-03-06T11:02:41Z ddc:004 open_access

Approximating Red-Blue Set Cover and Minimum Monotone Satisfying Assignment Chlamtáč, Eden Makarychev, Yury Vakilian, Ali Red-Blue Set Cover Problem Circuit Minimum Monotone Satisfying Assignment (MMSA) Problem LP Rounding 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^{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/32^{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 → ∞. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eden Chlamtáč and Yury Makarychev and Ali Vakilian 2023 Is Part Of LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2023.11 urn:nbn:de:0030-drops-188366 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.11 eng https://creativecommons.org/licenses/by/4.0/legalcode